समस्या कथन
एक संख्या N दी गई है। 1 से N के बीच के न्यूनतम तत्वों की संख्या ढूंढें जिन्हें हटाया जाए ताकि शेष तत्वों से प्राप्त XOR अधिकतम हो।
एल्गोरिदम
1. यदि n 1 या 2 है तो किसी तत्व को हटाने की आवश्यकता नहीं है। उत्तर शून्य है। 2. एक संख्या ढूंढें जो 2 की घात है और n से बड़ी या बराबर है। इसे nextNumber कहें। 2.1. यदि n == nextNumber या n == (nextNumber - 1) तो उत्तर 1 है 2.2. यदि n == (nextNumber - 2) तो उत्तर 0 है 3. यदि n सम है तो उत्तर 1 अन्यथा 2
C++ उदाहरण
#include <iostream>
using namespace std;
int nextPowerOf2(int n) {
if (n && !(n & (n - 1))) return n;
int cnt = 0;
while (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