C++ หาตัวเลขที่ Sum of XOR กับช่วงอาร์เรย์มากที่สุด

เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์และคำถาม (Queries) บางอย่าง ตอนนี้ในแต่ละคำถาม เราได้รับช่วง (Range) ตอนนี้เราต้องหาตัวเลขที่ทำให้ผลรวมของ XOR ของพวกเขากับ x เป็นค่าสูงสุด เช่น

Input : A = {20, 11, 18, 2, 13} Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629 2147483645 2147483645

ในปัญหานี้ เราจะใช้ Prefix Count ของ 1's ที่อยู่ในตัวเลขที่แต่ละตำแหน่ง ตอนนี้เราได้ Pre-calculate จำนวน 1's แล้ว สำหรับการหาจำนวน 1's ในช่วงที่กำหนดจาก L ถึง R เราต้องลบ Prefix จนถึง R ด้วย Prefix จนถึง L

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

ในวิธีนี้ เนื่องจากเราต้องการหาผลรวมสูงสุด เราจึงต้องทำให้บิตส่วนใหญ่ของ XOR เป็น 1 ดังนั้นเราตรวจสอบว่า สำหรับบิตใดก็ตาม ถ้าจำนวน 1's มากกว่าจำนวน 0's เราจะรีเซ็ตบิตนั้นของ x เนื่องจากตัวเลขส่วนใหญ่มีบิตนั้นเป็น 1 ตอนจับคู่ 1's ส่วนใหญ่กับ 0's เราก็จะได้บิตส่วนใหญ่เป็น 1 และนั่นคือวิธีที่เราเพิ่มคำตอบให้สูงสุด

ตัวอย่าง

โค้ด C++ สำหรับวิธีการข้างต้น

#include <bits/stdc++.h> 
using namespace std; 

#define MAX 2147483647 
int prefix[100001][32]; 

void prefix_bit(int A[], int n){ 
    for (int j = 0; j < 32; j++) 
        prefix[0][j] = 0; 
    for (int i = 1; i <= n; i++){ 
        int a = A[i - 1]; 
        for (int j = 0; j < 32; j++){ 
            int x = 1 << j; 
            if (a & x) 
                prefix[i][j] = 1 + prefix[i - 1][j]; 
            else 
                prefix[i][j] = prefix[i - 1][j]; 
        } 
    } 
} 

int maximum_num(int l, int r){ 
    int numberofbits = r - l + 1; 
    int X = MAX; 
    for (int i = 0; i < 31; i++){ 
        int x = prefix[r][i] - prefix[l - 1][i]; 
        if (x >= numberofbits - x){ 
            int currentbit = 1 << i; 
            X = X ^ currentbit; 
        } 
    } 
    return X; 
} 

int main(){ 
    int n = 5, q = 3; 
    int A[] = { 210, 11, 48, 22, 133 }; 
    int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; 
    prefix_bit(A, n); 
    for (int i = 0; i < q; i++) 
        cout << maximum_num(L[i], R[i]) << "\n"; 
    return 0; 
}

ผลลัพธ์

2147483629 2147483647 2147483629

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

ในวิธีนี้ เราคำนวณ Prefix Count ของ 1's สำหรับแต่ละบิตก่อน ตอนนี้เราได้ Count แล้ว เราแก้ปัญหาที่ใหญ่ที่สุดคือการวนลูปผ่านคำถาม ตอนนี้เราไม่ต้องวนลูปผ่านแต่ละช่วงแล้ว เราสามารถคำนวณได้ผ่าน Prefix Array ตรรกะหลักคือ เราคำนวณจำนวนบิตที่เป็น 1 และ 0 ในช่วง ตอนที่เราเจอตำแหน่งที่จำนวน 1's มากกว่าจำนวน 0's เราจะรีเซ็ตบิตนั้นใน x ตอนนี้เราเริ่มต้น x ด้วย 2^31 - 1 ดังนั้นบิตทั้งหมดจะเป็น 1 และเราหาคำตอบโดยการ Toggle บิตใน x

สรุป

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