C++ ব্যবহার করে XOR সর্বোচ্চ করার জন্য ন্যূনতম এলিমেন্ট অপসারণ

সমস্যা বিবরণ

একটি সংখ্যা N দেওয়া আছে। ১ থেকে N পর্যন্ত এর মাঝপথে ন্যূনতম কতগুলো এলিমেন্ট অপসারণ করলে বাকি এলিমেন্টগুলোর XOR সর্বোচ্চ হবে তা বের করতে হবে।

এলগরিদম

1. যদি n ১ বা ২ হয় তবে কোনো এলিমেন্ট অপসারণ দরকার নয়, উত্তর ০
2. n-এর চেয়ে বড় বা সমান একটি ২-এর ঘাত বের করুন। এটিকে nextNumber বলুন
   2.1. যদি n == nextNumber বা n == (nextNumber - 1) হয় তবে উত্তর ১
   2.2. যদি n == (nextNumber - 2) হয় তবে উত্তর ০
3. যদি n বিজোড় হয় তবে উত্তর ২ অন্যথায় ১

উদাহরণ কোড

#include <iostream>
using namespace std;

int nextPowerOf2(int n) {
    if (n && !(n & (n - 1))) {
        return n;
    }
    int cnt = 0;
    while (n) {
        n = n / 2;
        ++cnt;
    }
    return (1 << cnt);
}

int elmentsToBeRemoved(int n) {
    if (n == 1 || n == 2) {
        return 0;
    }
    int nextNumber = nextPowerOf2(n);
    if (n == nextNumber || n == nextNumber - 1) {
        return 1;
    } else if (n == nextNumber - 2) {
        return 0;
    } else if (n & 1) {
        return 2;
    } else {
        return 1;
    }
}

int main() {
    int n = 10;
    cout << "Numbers to be removed = " << elmentsToBeRemoved(n) << endl;
    return 0;
}

আউটপুট

প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:

Numbers to be removed = 1