XORed योग का अधिकतम संभव मूल्य खोजने के लिए C++ प्रोग्राम

मान लीजिए कि हमारे पास N तत्वों के साथ एक सरणी A है और दूसरा मान K है। 0 से K तक के पूर्णांक X के लिए, f(X) =(X xor A[1]) + (X xor A[2]) + .. + (एक्स एक्सओआर ए [एन])। हमें f का अधिकतम संभव मान ज्ञात करना है।

इसलिए, यदि इनपुट K =7 जैसा है; A =[1, 6, 3], तो आउटपुट 14 होगा, क्योंकि f(4) =(4 XOR 1) + (4 XOR 6) + (4 XOR 3) =5 + 2 + 7 =14.

कदम

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n := size of A
for initialize i := 45, when i >= 0, update (decrease i by 1), do:
   p := 2^i
   m := 0
   for initialize j := 0, when j < n, update (increase j by 1), do:
      if A[j] AND p is non-zero, then:
         (increase m by 1)
   if o + p <= k, then:
      if m < n - m, then:
         m := n - m
         o := o + p
   d := d + p * m
return d

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;

long solve(int k, vector<int> A){
   long n = A.size(), d = 0, m, p, o = 0;
   for (long i = 45; i >= 0; i--){
      p = pow(2, i);
      m = 0;
      for (int j = 0; j < n; j++){
         if (A[j] & p)
            m++;
      }
      if (o + p <= k){
         if (m < n - m){
            m = n - m;
            o += p;
         }
      }
      d += p * m;
   }
   return d;
}
int main(){
   int K = 7;
   vector<int> A = { 1, 6, 3 };
   cout << solve(K, A) << endl;
}

इनपुट

7, { 1, 6, 3 }

आउटपुट

14