Cho a, b. Tìm giá trị nhỏ nhất của (a XOR x) + (b XOR x) với x bất kỳ.
Ví dụ
Với a=6, b=12, đầu ra 10. Chọn x=4: (6^4)+(12^4)=2+8=10.
Giải thuật
Kết quả luôn bằng a XOR b. Chứng minh: (a^x)+(b^x) = (a^b) + 2*(~(a^b)&(a^x)) ≥ a^b. Đạt khi x = a & b (hoặc các giá trị khác).
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b) {
return (a ^ b);
}
int main() {
int a = 6, b = 12;
cout << solve(a, b) << endl;
}
Đầu vào / Đầu ra
Input: 6, 12
Output: 10