ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของ XOR ของผลรวมของคู่ทั้งหมดในอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: arr[5, 7, 9]
ผลลัพธ์: 22
คำอธิบาย:
(5+5) ^ (5+7) ^ (5+9) ^ (7+5) ^ (7+7) ^ (7+9) ^ (9+5) ^ (9+7) ^ (9+9) =22
วิธีแก้ปัญหาอย่างง่ายคือการใช้การวนซ้ำซ้อน และสร้างคู่ที่เป็นไปได้ทั้งหมดจากอาร์เรย์ และคำนวณ XOR ของผลรวมของแต่ละคู่
อัลกอริทึม:
เริ่มต้น XorSum =0
ขั้นตอนที่ 1: วนซ้ำจาก 0 ถึง n ติดตาม:
ขั้นตอนที่ 1.1: วนซ้ำจาก 0 ถึง n ติดตาม
ขั้นตอนที่ 1.1.1: อัปเดต XorSum เช่น XorSum =XorSum ^ (arr[i]+arr[j])
ขั้นตอนที่ 2: ผลตอบแทนรวม
โปรแกรมแสดงการทำงานของโค้ดของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
XorSum = XorSum^(arr[i]+arr[j]);
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
return 0;
} ผลลัพธ์
XOR of sum of all pairs in an array is 22
วิธีแก้ปัญหานี้ไม่มีประสิทธิภาพเนื่องจากความซับซ้อนของเวลาอยู่ในลำดับ n 2 .
โซลูชันที่มีประสิทธิภาพคือการใช้คุณสมบัติของ XOR ในการแก้ปัญหา เราจะคำนวณ XOR ขององค์ประกอบทั้งหมดในอาร์เรย์แล้วคูณด้วยสอง
อัลกอริทึม:
เริ่มต้น XorSum =0
ขั้นตอนที่ 1: วนซ้ำจาก 0 ถึง n.
ขั้นตอนที่ 1.1: อัปเดต XorSum เช่น XorSum =XorSum ^ arr[i]
ขั้นตอนที่ 2: เพิ่มเป็นสองเท่าและส่งคืน
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
XorSum = XorSum^arr[i];
XorSum = 2*XorSum;
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"XOR of sum of all pairs in an array is "<<findSumXORPair(arr, n);
return 0;
} ผลลัพธ์
XOR of sum of all pairs in an array is 22
