C++ การค้นหา XOR ของตัวหารคี่มากสุดในช่วงที่กำหนด

ได้รับอาร์เรย์ของจำนวนเต็ม N ตัวและ Q คำถามเกี่ยวกับช่วงข้อมูล สำหรับแต่ละคำถาม เราต้องคืนค่า XOR ของตัวหารคี่มากสุดของแต่ละจำนวนในช่วงนั้น

ตัวหารคี่มากสุด คือจำนวนคี่ที่มากที่สุดซึ่งหารจำนวน N ลงตัว เช่น ตัวหารคี่มากสุดของ 6 คือ 3

Input: nums[ ] = { 3, 6, 7, 10 }, query[ ] = { { 0, 2 }, { 1, 3 } } Output: query1: 7 query2: 1 Explanation: ตัวหารคี่มากสุดของอาร์เรย์ nums คือ { 3, 3, 7, 5 } สำหรับ query 1 เราต้องหา XOR ของดัชนี 0, 1, และ 2 ซึ่งได้ 7 และสำหรับ query 2 ต้องหา XOR ของดัชนี 1, 2, และ 3 ซึ่งได้ 1

วิธีการแก้ปัญหา

วิธีง่าย (Simple Approach)

ในวิธีนี้ เราจะหาตัวหารคี่มากสุดของทุกสมาชิกในอาร์เรย์ก่อน จากนั้นตามช่วงของคำถาม ให้คำนวณ XOR ของแต่ละสมาชิกในช่วงและคืนค่าผลลัพธ์

วิธีมีประสิทธิภาพ (Efficient Approach)

วิธีที่มีประสิทธิภาพกว่าคือการสร้างอาร์เรย์ Prefix XOR (prefix_XOR[]) จากอาร์เรย์ที่เก็บตัวหารคี่มากสุด แทนที่จะคำนวณ XOR ทุกครั้งในช่วง เราสามารถใช้ prefix_XOR[R] ^ prefix_XOR[L-1] ได้ทันที (หมายเหตุ: XOR ใช้ ^ ไม่ใช่ -)

อาร์เรย์ Prefix XOR คืออาร์เรย์ที่แต่ละสมาชิกเก็บค่า XOR สะสมของสมาชิกก่อนหน้าทั้งหมด

ตัวอย่างโค้ด C++

#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]; 
    
    // สร้างอาร์เรย์เก็บตัวหารคี่มากสุดของแต่ละสมาชิก
    for (int i = 0; i < n; i++) { 
        while (nums[i] % 2 != 1) 
            nums[i] /= 2; 
        prefix_XOR[i] = nums[i]; 
    } 
    
    // แปลงเป็นอาร์เรย์ Prefix XOR
    for (int i = 1; i < n; i++) 
        prefix_XOR[i] = prefix_XOR[i - 1] ^ prefix_XOR[i]; 
    
    // อาร์เรย์คำถาม
    int query[2][2] = {{0, 2},{1, 3}}; 
    int q = sizeof(query) / sizeof(query[0]); 
    
    // คำนวณผลลัพธ์ของแต่ละคำถาม
    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[i][1]] ^ prefix_XOR[query[i][0] - 1]; 
            cout << result << endl; 
        } 
    } 
    return 0; 
}

ผลลัพธ์

7
1

คำอธิบายโค้ด

• สร้างอาร์เรย์ prefix_XOR เพื่อเก็บตัวหารคี่มากสุดของแต่ละสมาชิก แล้วแปลงเป็นอาร์เรย์ Prefix XOR

• คำนวณตัวหารคี่มากสุดโดยการหารด้วย 2 ซ้ำจนกว่า modulo 2 จะได้ 1

• สร้าง Prefix XOR โดยวนลูปผ่านอาร์เรย์และทำ XOR ระหว่างสมาชิกปัจจุบันกับสมาชิกก่อนหน้า

• ผลลัพธ์ของคำถามคำนวณจาก prefix_XOR[R] ^ prefix_XOR[L-1] (กรณี L=0 ใช้ prefix_XOR[R] โดยตรง)

สรุป

ในบทช่วยสอนนี้ เราได้อภิบัติปัญหาการหา XOR ของตัวหารคี่มากสุดในช่วงของอาร์เรย์ เราได้เสนอวิธีแก้ปัญหาโดยการหาตัวหารคี่มากสุดของแต่ละสมาชิกและใช้เทคนิค Prefix XOR Array เรายังได้แสดงโปรแกรม C++ สำหรับปัญหานี้ ซึ่งสามารถนำไปใช้กับภาษาอื่น เช่น C, Java, Python ได้เช่นกัน หวังว่าบทความนี้จะเป็นประโยชน์