ค้นหาค่า XOR สูงสุดของอาร์เรย์ย่อยขนาด k ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วย n องค์ประกอบและจำนวนเต็ม k งานของเราคือการหาค่า XOR สูงสุดของอาร์เรย์ย่อยขนาด k

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

arr[] ={3, 1, 6, 2 ,7, 9} k =3

ผลลัพธ์

คำอธิบาย

อาร์เรย์ย่อยทั้งหมดและ xor ขององค์ประกอบทั้งหมดที่มีขนาด k

<ก่อน>{3, 1, 6} =4{1, 6, 2} =5{6, 2, 7} =3{2, 7, 9} =12

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการใช้สองลูป หนึ่งเพื่อวนซ้ำบนอาร์เรย์และอื่น ๆ เพื่อค้นหา XOR ขององค์ประกอบทั้งหมดของ subarray แล้วคืนค่าสูงสุดของทั้งหมด

วิธีแก้ปัญหานี้ใช้ได้ แต่สามารถหาแนวทางแก้ไขปัญหาที่ดีกว่าได้ เราต้องหาผลรวมโดยเริ่มจาก subarray ของ size k เริ่มจาก

ดัชนี 0 จากนั้นวนซ้ำอาร์เรย์และเพิ่มองค์ประกอบใหม่ให้กับ XOR และลบองค์ประกอบแรก การลบทำได้โดยใช้สูตร x^a^x =a.

ดังนั้น สำหรับการโต้ตอบแต่ละครั้ง เราจะดำเนินการก่อน XOR ^ arr[i - k] ซึ่งจะให้ค่าของอาร์เรย์ย่อยจากดัชนีล่าสุด + 1 ถึงดัชนีปัจจุบัน - 1

จากนั้นเราจะดำเนินการ XOR ของ subarray ด้วย arr[i] เพื่อรับ XOR ปัจจุบัน เราจะค้นหาและคืนค่าสูงสุดจาก XOR ทั้งหมด

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#includeใช้เนมสเปซ std;int findMaxSubArrayXOR(int arr[] , int n , int k) { int currentXORVal =0; สำหรับ (int i =0; i  ผลลัพธ์
 XOR สูงสุดของ subarray ขนาด 3 คือ 12