แนวคิด
สำหรับอาร์เรย์ที่กำหนด Arr[] ของจำนวนเต็มที่ไม่เป็นลบ ภารกิจคือการกำหนดจำนวนเต็ม X ที่ (Arr[0] XOR X) + (Arr[1] XOR X) + … + Arr[n – 1] XOR X เป็นไปได้น้อยที่สุด
ป้อนข้อมูล
Arr[] = {3, 4, 5, 6, 7} ผลผลิต
X = 7, Sum = 10
แนวทาง
ดังนั้นเราจะตรวจสอบ 'i'th bit ของทุก ๆ จำนวนอาร์เรย์ในการแทนค่าไบนารีและพิจารณาและนับตัวเลขเหล่านั้นที่มี 'i'th bit ที่ตั้งค่าเป็น '1' เนื่องจากบิตชุดเหล่านี้จะช่วยเพิ่มผลรวมสูงสุดแทนที่จะย่อเล็กสุด ด้วยเหตุนี้ เราจึงต้องสร้างเซ็ตนี้จาก 'i'th bit to '0' หากจำนวนมากกว่า N/2 และหากการนับน้อยกว่า N/2 แสดงว่าตัวเลขที่มี 'ชุดบิตที่ i' จะน้อยกว่า และด้วยเหตุนี้จึงไม่มีผลกับคำตอบ เราทราบตามการดำเนินการ XOR ในสองบิต เมื่อ A XOR B และทั้ง A และ B เหมือนกัน ผลลัพธ์จะเป็น '0' ดังนั้นเราจะสร้าง 'i'th bit ในจำนวนของเรา (num) ถึง '1' ส่งผลให้ (1 XOR 1) ให้ '0' และลดจำนวนรวมให้เหลือน้อยที่สุด
ตัวอย่าง
// 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
