ধরুন আমাদের কাছে 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 := 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