সি++-এ সমান যোগফল এবং XOR

এই সমস্যায় আমাদের একটি পূর্ণসংখ্যা n দেওয়া হয়েছে। আমাদের কাজ হলো i = 0 থেকে n পর্যন্ত এমন পূর্ণসংখ্যার সংখ্যা বের করা যেখানে যোগফল XOR-এর সমান অর্থাৎ (n+i) = (n^i)।

উদাহরণ দিয়ে বুঝি

ইনপুট: n = 4

আউটপুট: ৪

ব্যাখ্যা:

i = 0 থেকে n পর্যন্ত সব মান বিবেচনা করলে,

i = 0,  4 + 0 = 4, 4^0 = 4
i = 1,  4 + 1 = 5, 4^1 = 5
i = 2,  4 + 2 = 6, 4^2 = 6
i = 3,  4 + 3 = 7, 4^3 = 7
i = 4,  4 + 4 = 8, 4^4 = 0
গণনা = ৪

সমাধানের পদ্ধতি

একটি সহজ সমাধান হলো n এবং i-এর যোগফল এবং n এবং i-এর XOR বের করা। এই দুটি মান তুলনা করে সমান হলে কাউন্ট বাড়ানো।

অ্যালগরিদম:

ধাপ ১: i = 0 থেকে n পর্যন্ত লুপ চালান।
ধাপ ১.১: (n + i) এর মান বের করুন।
ধাপ ১.২: (n^i) এর মান বের করুন।
ধাপ ১.৩: ধাপ ১.১ এবং ১.২-এর মান তুলনা করুন।
ধাপ ১.৪: যদি সমান হয়, কাউন্ট বাড়ান।
ধাপ ২: কাউন্ট মান প্রিন্ট করুন।

সমাধান minhaj করার প্রোগ্রাম (প্রথম পদ্ধতি)

#include <iostream> 
using namespace std; 

int main() { 
    int n = 5; 
    int counter = 0; 
    for(int i=0; i<=n; i++ ) 
        if ( (n+i) == (n^i) ) 
            counter++; 
    cout << "The count of integers with equal sum and XOR is " << counter; 
    return 0; 
}

আউটপুট

The count of integers with equal sum and XOR is 2

এই পদ্ধতিটি ভালো কিন্তু আরও ভালো সমাধান আছে, যা এই তথ্যের উপর ভিত্তি করে:

যদি n^i = n+i, তবে n&i = 0।

যদি n&i = 0 হয়, তবে দুটি সংখ্যার সেট এবং আনসেট বিট বিপরীত হবে। এবং আমাদের এমন মানগুলোর সংখ্যা গণনা করতে হবে। তার জন্য প্রোগ্রাম:

দ্বিতীয় পদ্ধতি

#include <iostream> 
using namespace std; 

int countValuesWithEqualSumXOR(int n) { 
    int countUnSetBits=0; 
    while (n) { 
        if ((n & 1) == 0) 
            countUnSetBits++; 
        n=n>>1; 
    } 
    return 1 << countUnSetBits; 
} 

int main() { 
    int n = 6; 
    cout << "The count of integers with equal sum and XOR is " << countValuesWithEqualSumXOR(n); 
    return 0; 
}

আউটপুট

The count of integers with equal sum and XOR is 2