การลดผลรวมอาร์เรย์โดยใช้การดำเนินการ XOR กับองค์ประกอบทั้งหมดของอาร์เรย์ใน C++

คำอธิบาย

เมื่อกำหนดขนาดอาร์เรย์ N ค้นหาองค์ประกอบ X โดยที่ผลรวมขององค์ประกอบอาร์เรย์ควรน้อยที่สุดเมื่อดำเนินการ XOR ด้วย X และแต่ละองค์ประกอบของอาร์เรย์

หากอินพุตอาร์เรย์คือ:arr [] ={8, 5, 7, 6, 9} ผลรวมขั้นต่ำจะเป็น 30 การแทนค่าไบนารีขององค์ประกอบอาร์เรย์คือ:8 :10005 :01017 :01116 :01019 :1001ถ้า X =5 แล้ว หลังจากดำเนินการผลรวม XOR จะเป็น 30:8 ^ 5 =135 ^ 5 =07 ^ 5 =26 ^ 5 =39 ^ 5 =12Sum =30 (13 + 0 + 2 + 3 + 12)

อัลกอริทึม

<ก่อน>1. สร้าง bitMap ขนาด 32 ในขณะที่เราใช้จำนวนเต็ม 32 บิต2 วนซ้ำในอาร์เรย์และสำหรับแต่ละองค์ประกอบของอาร์เรย์:หากมีการตั้งค่าบิตที่ 0 ขององค์ประกอบ การเพิ่มจำนวน bitMap[0] b หากมีการตั้งค่าบิตที่ 1 ขององค์ประกอบ ให้เพิ่มจำนวนบิตแมป[1] และอื่นๆ3 ตอนนี้หา X โดยวนซ้ำบนอาร์เรย์ bitMap ดังนี้:ถ้า bitMap[i]> n/2:แล้วX =X + pow(2, i);4. วนซ้ำผ่านอาร์เรย์อินพุต ดำเนินการ XOR ด้วย X และแต่ละองค์ประกอบของอาร์เรย์5 คำนวณผลรวมขององค์ประกอบอาร์เรย์

ตัวอย่าง

#include #include #include using เนมสเปซ std;#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))const int MAX_SIZE =32;int getSum (int *arr, int n){ int bitMap[MAX_SIZE]; int bitLength =0; int sum =0; ความละเอียดภายใน =0; กรอก (bitMap, bitMap + n, 0); สำหรับ (int i =0; i  0) { int rem =num % 2; นัม =นัม / 2; ถ้า (rem ==1) { bitMap[f]++; } ++f; bitLength =สูงสุด (bitLength, f); } } int ผู้สมัคร =0; สำหรับ (int i =0; i  n / 2) { ผู้สมัคร +=num; } } สำหรับ (int i =0; i  ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 ผลรวมขั้นต่ำ:30