मान लीजिए हमारे पास N तत्वों वाला एक ऐरे A है और एक अन्य मान K है। 0 से K की रेंज में एक पूर्णांक X के लिए, मान लें f(X) = (X xor A[1]) + (X xor A[2]) + ... + (X xor A[N])। हमें f का अधिकतम संभव मान ढूंढना है।
उदाहरण के लिए, यदि इनपुट K = 7; A = [1, 6, 3] है, तो आउटपुट 14 होगा, क्योंकि f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := A का आकार i := 45 से 0 तक, करें: p := 2^i m := 0 j := 0 से n-1 तक, करें: यदि A[j] AND p शून्येतर है, तो: m बढ़ाएं यदि o + p <= k, तो: यदि m < n - m, तो: m := n - m o := o + p d := d + p * m 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
