สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ N และอีกค่าหนึ่ง K สำหรับจำนวนเต็ม X ในช่วง 0 ถึง K ให้ 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
