ลดผลรวมอาร์เรย์ให้น้อยที่สุดด้วยการ XOR ใน C++

ปัญหา

ให้อาร์เรย์ขนาด N หาค่า X ที่ทำให้ผลรวมของ (arr[i] XOR X) น้อยที่สุด

ตัวอย่าง: arr = [8, 5, 7, 6, 9]

ถ้า X = 5:

8^5=13, 5^5=0, 7^5=2, 6^5=3, 9^5=12
ผลรวม = 13+0+2+3+12 = 30 (น้อยที่สุด)

วิธีแก้ปัญหา: Bitwise Analysis

พิจารณาแต่ละบิตแยกกัน (32 บิตสำหรับ int):

บิตที่ i: นับจำนวนสมาชิกที่มีบิต i = 1 (เป็น count[i])
ถ้า count[i] > N/2: เซตบิต i ของ X = 1 (เพื่อให้ผลลัพธ์ส่วนใหญ่เป็น 0)
ถ้า count[i] ≤ N/2: เซตบิต i ของ X = 0

เหตุผล: XOR กับ 1 จะกลับบิต, XOR กับ 0 จะคงบิต ต้องการให้ผลลัพธ์มี 0 มากที่สุด

ตัวอย่างโค้ด C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minimizeXorSum(vector<int>& arr) {
    const int BITS = 32;
    int bitCount[BITS] = {0};
    int n = arr.size();
    
    // นับบิต 1 ในแต่ละตำแหน่ง
    for (int num : arr) {
        for (int i = 0; i < BITS; i++) {
            if (num & (1 << i))
                bitCount[i]++;
        }
    }
    
    // สร้าง X
    int X = 0;
    for (int i = 0; i < BITS; i++) {
        if (bitCount[i] > n / 2)
            X |= (1 << i);
    }
    
    // คำนวณผลรวม
    long long sum = 0;
    for (int num : arr)
        sum += (num ^ X);
    
    cout << "Optimal X = " << X << endl;
    return sum;
}

int main() {
    vector<int> arr = {8, 5, 7, 6, 9};
    cout << "Minimum sum = " << minimizeXorSum(arr) << endl;
    return 0;
}

ผลลัพธ์

Optimal X = 5
Minimum sum = 30

การวิเคราะห์ตัวอย่าง

Number	Binary	Bit 3	Bit 2	Bit 1	Bit 0
8	1000	1	0	0	0
5	0101	0	1	0	1
7	0111	0	1	1	1
6	0110	0	1	1	0
9	1001	1	0	0	1
Count of 1s		2	3	2	3
> N/2 (2.5)?		No	Yes	No	Yes
X bits		0	1	0	1

X = 0101₂ = 5 ✓

ความซับซ้อน

เวลา: O(N × BITS) = O(32N) ≈ O(N)
พื้นที่: O(1) เพิ่มเติม