Giả sử chúng ta có một mảng A với N phần tử và một giá trị khác K. Với một số nguyên X trong phạm vi từ 0 đến K, cho f (X) =(X xor A [1]) + (X xor A [2]) + .. . + (X xor A [N]). Chúng ta phải tìm giá trị lớn nhất có thể có của f.
Vì vậy, nếu đầu vào giống như K =7; A =[1, 6, 3], thì đầu ra sẽ là 14, vì f (4) =(4 XOR 1) + (4 XOR 6) + (4 XOR 3) =5 + 2 + 7 =14.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
7, { 1, 6, 3 } Đầu ra
14