ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของ n ตัวเลข งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของ XOR ของอาร์เรย์ย่อยทั้งหมดของอาร์เรย์
ที่นี่ เราจำเป็นต้องค้นหาอาร์เรย์ย่อยทั้งหมดของอาร์เรย์ที่กำหนด จากนั้นสำหรับแต่ละอาร์เรย์ย่อย เราจะค้นหา xor ขององค์ประกอบและเพิ่มค่า XOR ให้กับตัวแปรผลรวม
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: arr[] = {5, 1, 4}
Output:
Explanation: XOR of all subarrays for the array :
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
Sum = 5 + 1 + 4 + 4 + 5 + 0 = 19 วิธีง่ายๆ ในการแก้ปัญหานี้คือการใช้ลูปถัดไปเพื่อค้นหาอาร์เรย์ย่อยทั้งหมด จากนั้นหา XOR ขององค์ประกอบของอาร์เรย์ย่อยและเพิ่มลงในตัวแปรผลรวม
โซลูชันนี้ไม่มีประสิทธิภาพเนื่องจากใช้การซ้อนลูปและจะมีความซับซ้อนของเวลาแบบเอ็กซ์โพเนนเชียล
วิธีที่มีประสิทธิภาพในการแก้ปัญหานี้คือการใช้อาร์เรย์นำหน้า อาร์เรย์นำหน้านี้จะเก็บ xor ขององค์ประกอบทั้งหมดของอาร์เรย์จนถึง i กล่าวคือ
prefixarr[i] = arr[0]^arr[1]^ … ^arr[i].
หลังจากนี้ เราสามารถใช้สูตรง่ายๆ เพื่อค้นหา XOR ขององค์ประกอบจากดัชนี i ถึง j
XOR(i-j) = prefixarr[j] - prefixarr[i]for i >= 0. If i = 0, XOR(i-j) = prefixarr[j]
โดยใช้สูตรนี้ เราจะหา XOR ของอาร์เรย์ย่อยทั้งหมด
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int calcSubArrayXORSum(int arr[], int n) {
int sum = 0;
int multiplier = 1;
for (int i = 0; i < 30; i++) {
int oddCount = 0;
bool isOdd = 0;
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
isOdd = (!isOdd);
if (isOdd)
oddCount++;
}
for (int j = 0; j < n; j++) {
sum += (multiplier * oddCount);
if ((arr[j] & (1 << i)) > 0)
oddCount = (n - j - oddCount);
}
multiplier *= 2;
}
return sum;
}
int main() {
int arr[] = { 3, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Sum of XOR of all subarrays is "<<calcSubArrayXORSum(arr, n);
return 0;
} ผลลัพธ์
Sum of XOR of all subarrays is 46
