กำหนดอาร์เรย์ของจำนวนเต็ม N และคิวรี Q ของช่วง สำหรับแต่ละข้อความค้นหา เราจำเป็นต้องคืนค่า XOR ของตัวหารคี่มากที่สุดของแต่ละตัวเลขในช่วง
ตัวหารคี่ที่มากที่สุดคือจำนวนคี่ที่มากที่สุดซึ่งสามารถหารจำนวน N ได้ เช่น ตัวอย่างเช่น ตัวหารคี่สูงสุดของ 6 คือ 3
Input: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } }
Output:
query1: 7
query2: 1
Explanation: greatest odd divisors of nums array are { 3, 3, 7, 5 }.
For query 1 we need to find the XOR of indexes 0, 1, and 2 which is 7, and for query2 we need to find XOR of indexes 1, 2, and 3 which is 1. แนวทางในการหาแนวทางแก้ไข
แนวทางง่ายๆ
อย่างแรก ด้วยวิธีง่าย ๆ เราต้องหาตัวหารคี่ที่ใหญ่ที่สุดขององค์ประกอบอาร์เรย์ทั้งหมด จากนั้นตามช่วงของการสืบค้น เราจำเป็นต้องคำนวณ XOR ของแต่ละองค์ประกอบในช่วงและส่งคืน
แนวทางที่มีประสิทธิภาพ
วิธีที่มีประสิทธิภาพในการแก้ปัญหานี้คือการสร้างคำนำหน้า XOR array prefix_XOR[] ของอาร์เรย์ที่มีตัวเลขตัวหารคี่มากที่สุด แทนที่จะทุกครั้งที่ค้นหา XOR ของแต่ละตัวเลขในช่วงและส่งคืน prefix_XOR[R] - prefix_XOR[L-1 ].
คำนำหน้า xor array คืออาร์เรย์ที่แต่ละองค์ประกอบมี xor ขององค์ประกอบก่อนหน้าทั้งหมด
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main(){
int nums[] = { 3, 6, 7, 10 };
int n = sizeof(nums) / sizeof(nums[0]);
int prefix_XOR[n];
// creating an array
// containing Greatest odd divisor of each element.
for (int i = 0; i < n; i++) {
while (nums[i] % 2 != 1)
nums[i] /= 2;
prefix_XOR[i] = nums[i];
}
// changing prefix_XOR array to prefix xor array.
for (int i = 1; i < n; i++)
prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i];
// query array to find result of these queries.
int query[2][2] = {{0, 2},{1, 3}};
int q = sizeof(query) / sizeof(query[0]);
// finding results of queries.
for(int i = 0;i<q;i++){
if (query[i][0] == 0)
cout<< prefix_XOR[query[i][1]] << endl;
else{
int result = prefix_XOR[query[0][1]] ^ prefix_XOR[query[i][0] - 1];
cout << result << endl;
}
}
return 0;
} ผลลัพธ์
7 4
คำอธิบายของโค้ดด้านบน
-
อาร์เรย์ prefix_XOR ถูกสร้างขึ้นเพื่อเก็บตัวหารคี่ที่ยิ่งใหญ่ที่สุดของแต่ละองค์ประกอบ แล้วเปลี่ยนอาร์เรย์นี้เป็นอาร์เรย์ XOR นำหน้า
-
ตัวหารคี่ที่ยิ่งใหญ่ที่สุดคำนวณโดยการหารด้วยสองจนกว่าจะได้โมดูโล 2 ให้ 1
-
Prefix xor array ถูกสร้างขึ้นโดยการสำรวจผ่านอาร์เรย์และทำ XOR ระดับบิตขององค์ประกอบปัจจุบันกับองค์ประกอบก่อนหน้า
-
ผลลัพธ์ของการค้นหาคำนวณโดยการลบดัชนีด้านขวาของอาร์เรย์ prefix_XOR[] ด้วย (ซ้าย - 1) ดัชนีของอาร์เรย์ prefix_XOR[]
บทสรุป
ในบทช่วยสอนนี้ เราได้พูดถึงปัญหาที่เราต้องหา XOR ของตัวหารคี่มากที่สุดของแต่ละตัวเลขในช่วงของอาร์เรย์ที่กำหนด เราได้พูดคุยถึงแนวทางในการแก้ปัญหานี้โดยการค้นหาตัวหารคี่ที่ยิ่งใหญ่ที่สุดของแต่ละองค์ประกอบ และใช้อาร์เรย์ xor นำหน้า เรายังพูดถึงโปรแกรม C++ สำหรับปัญหานี้ ซึ่งเราสามารถทำได้ด้วยภาษาโปรแกรม เช่น C, Java, Python เป็นต้น เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
