C++ का उपयोग करके XOR को अधिकतम बनाने के लिए हटाए जाने वाले तत्वों की न्यूनतम संख्या।

समस्या कथन

एक संख्या N को देखते हुए। कार्य N के बीच में हटाए जाने वाले तत्वों की न्यूनतम संख्या को खोजना है ताकि शेष तत्वों से प्राप्त XOR अधिकतम हो।

एल्गोरिदम

1. If n is 1 or 2 then there is no need to remove any element. Hence answer is zero
2. Find a number which is power of 2 and greater than or equal to. Let us call this number as nextNumber
   2.1. If n == nextNumber or n == (nextNumber – 1) then answer is 1
   2.2. If n = (nextNumber -2) then answer is 0
3. If n is an even then answer is 1 otherwise 2

उदाहरण

#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 = 1s