ในปัญหานี้ เราจะได้รับอาร์เรย์ของ n องค์ประกอบ งานของเราคือพิมพ์ XOR ของ XOR อาร์เรย์ย่อยที่เป็นไปได้ทั้งหมด (ตามลำดับ) ที่สร้างขึ้นจากองค์ประกอบของอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − อาร์เรย์ ={1, 3, 6, 8}
ผลผลิต − 0
คำอธิบาย −
(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6)^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)
ในการแก้ปัญหานี้ วิธีแก้ไขง่ายๆ อาจวนซ้ำในอาร์เรย์ย่อยทั้งหมดและค้นหา xors แต่นี่เป็นแนวทางที่ไม่มีประสิทธิภาพ วิธีที่ดีกว่าคือการนับความถี่ของแต่ละองค์ประกอบของอาร์เรย์ที่เกิดขึ้นในอาร์เรย์ย่อยทั้งหมด และใช้คุณสมบัติของ xor − xor ขององค์ประกอบ จำนวนครั้งคู่เท่ากับ 0 . เมื่อใช้สิ่งนี้ เราจะละเว้นค่าทั้งหมดที่เกิดขึ้นเป็นจำนวนคู่ในรายการอาร์เรย์ย่อย ตอนนี้องค์ประกอบที่มีความถี่การเกิดคี่จะถูกนำมาพิจารณา เช่น xor ขององค์ประกอบที่มีความถี่การเกิดคี่จะให้ผลลัพธ์สุดท้าย
ในการค้นหาการเกิดขึ้นของแต่ละองค์ประกอบของอาร์เรย์ในอาร์เรย์ย่อย เราจะใช้สูตรนี้ (i+1)*(n-i) .
เมื่อใช้สูตรนี้ เราจะหาความถี่ของการเกิดขึ้นของแต่ละองค์ประกอบ แล้วพิจารณาองค์ประกอบเหล่านั้นที่มีความถี่คี่ xor เพื่อให้ได้ผลลัพธ์สุดท้าย
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#include <iostream>
using namespace std;
int xorSubarrayXors(int arr[], int N){
int result = 0;
for (int i = 0; i < N; i++){
int freqency = (i + 1) * (N - i);
if (freqency % 2 == 1)
result ^= arr[i];
}
return result;
}
int main() {
int arr[] = {1, 3, 6, 8};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The xor of all subarray xors is : "<<xorSubarrayXors(arr, N);
return 0;
} ผลลัพธ์
The xor of all subarray xors is : 0
