หาค่าที่ทำให้ผลรวม XOR กับทุกค่าในอาร์เรย์เป็นค่าต่ำสุดใน C++

แนวคิด

เมื่อได้รับอาร์เรย์ Arr[] ของจำนวนเต็มบวก งานคือการหาจำนวนเต็ม X ที่ทำให้ (Arr[0] XOR X) + (Arr[1] XOR X) + … + (Arr[n-1] XOR X) ให้ค่าต่ำสุด

วิธีการแก้ปัญหา

เราจะตรวจสอบบิตที่ i ของทุกตัวเลขในอาร์เรย์ในรูปแบบไบนารี และนับจำนวนตัวเลขที่มีบิตที่ i ตั้งค่าเป็น 1 เพราะบิตเหล่านี้จะทำให้ผลรวมเพิ่มขึ้นแทนที่จะลดลง ดังนั้นเราต้องสร้างบิตที่ i ในตัวเลขของเรา (num) เป็น 0 หากจำนวนนับมากกว่า N/2 และหากจำนวนนับน้อยกว่า N/2 หมายความว่าตัวเลขที่มีบิตที่ i ตั้งค่านั้นน้อยกว่า จึงไม่ส่งผลต่อคำตอบ เราทราบว่าตามการดำเนินการ XOR เมื่อ A XOR B และ A, B เหมือนกัน ผลลัพธ์จะเป็น 0 ดังนั้นเราจะสร้างบิตที่ i ในตัวเลขของเราเป็น 1 เพื่อให้ (1 XOR 1) ให้ 0 และลดผลรวมลง

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

// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;

void findX1(int arr1[], int n1){
    int* itr1 = max_element(arr1, arr1 + n1);
    int p1 = log2(*itr1) + 1;
    int X1 = 0;
    for (int i = 0; i < p1; i++) {
        int count1 = 0;
        for (int j = 0; j < n1; j++) {
            if (arr1[j] & (1 << i)) {
                count1++;
            }
        }
        if (count1 > (n1 / 2)) {
            X1 += 1 << i;
        }
    }
    long long int sum1 = 0;
    for (int i = 0; i < n1; i++)
        sum1 += (X1 ^ arr1[i]);
    cout << "X = " << X1 << ", Sum = " << sum1;
}

// Driver code
int main(){
    int arr1[] = { 3, 4, 5, 6, 7 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    findX1(arr1, n1);
    return 0;
}

ผลลัพธ์

X = 7, Sum = 10