หาจำนวนซับอาร์เรย์ที่มี Bitwise OR มากกว่าหรือเท่ากับ K ด้วย C++

ในบทความนี้ เราจะอธิบายวิธีแก้ปัญหาการหาจำนวนซับอาร์เรย์ที่มี Bitwise OR มากกว่าหรือเท่ากับ K ด้วย C++ โจทย์ให้มาอาร์เรย์ arr[] และจำนวนเต็ม K เราต้องหาจำนวนซับอาร์เรย์ที่มี OR (Bitwise OR) มากกว่าหรือเท่ากับ K ตัวอย่างดังนี้:

Input: arr[] = {1, 2, 3} K = 3 Output: 4 Bitwise OR ของซับอาร์เรย์: {1} = 1, {1, 2} = 3, {1, 2, 3} = 3, {2} = 2, {2, 3} = 3, {3} = 3 มี 4 ซับอาร์เรย์ที่มี Bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6 Output: 2

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

เราจะใช้สองวิธีที่แตกต่างกันในการแก้ปัญหาด้วย C++:

1. วิธี Brute Force

ในวิธีนี้ เราจะตรวจสอบซับอาร์เรย์ทุกชุดที่สร้างได้ และตรวจสอบว่า OR มากกว่าหรือเท่ากับ K หรือไม่ หากใช่ ให้เพิ่มคำตอบ

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

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

int main() {
    int arr[] = {1, 2, 3}; // อาร์เรย์ที่กำหนด
    int k = 3;
    int size = sizeof(arr) / sizeof(int); // ขนาดอาร์เรย์
    int answer = 0; // ตัวนับคำตอบ
    
    for(int i = 0; i < size; i++) {
        int bitwise = 0; // ตัวแปรเปรียบเทียบกับ K
        for(int j = i; j < size; j++) { // ซับอาร์เรย์ทั้งหมดที่เริ่มจาก i
            bitwise = bitwise | arr[j];
            if(bitwise >= k) // หาก bitwise ≥ k ให้เพิ่มคำตอบ
                answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}

ผลลัพธ์

4

วิธีนี้ง่าย แต่มีข้อบกพร่อง คือ ไม่เหมาะสำหรับข้อจำกัดขนาดใหญ่ เพราะจะใช้เวลามากเกินไป ความซับซ้อนด้านเวลาคือ O(N²) โดย N คือขนาดอาร์เรย์ที่กำหนด จึงต้องหาวิธีที่มีประสิทธิภาพมากขึ้น

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

ในวิธีนี้ เราใช้คุณสมบัติของตัวดำเนินการ OR ซึ่งคือ ไม่มีการลดลงแม้จะเพิ่มตัวเลขเข้าไป กล่าวคือ หากเราได้ซับอาร์เรย์จาก i ถึง j ที่มี OR มากกว่าหรือเท่ากับ K ซับอาร์เรย์ทุกชุดที่ครอบคลุมช่วง {i,j} จะมี OR มากกว่า K เช่นกัน เราใช้ประโยชน์จากคุณสมบัตินี้เพื่อปรับปรุงโค้ด

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

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

int t[4*N];

void build(int* a, int v, int start, int end) { // สร้าง Segment Tree
    if(start == end) {
        t[v] = a[start];
        return;
    }
    int mid = (start + end)/2;
    build(a, 2 * v, start, mid);
    build(a, 2 * v + 1, mid + 1, end);
    t[v] = t[2 * v] | t[2 * v + 1];
}

int query(int v, int tl, int tr, int l, int r) { // ประมวลผลคิวรี/ซับอาร์เรย์
    if (l > r)
        return 0;
    if(tl == l && tr == r)
        return t[v];
    int tm = (tl + tr)/2;
    int q1 = query(2*v, tl, tm, l, min(tm, r));
    int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
    return q1 | q2;
}

int main() {
    int arr[] = {1, 2, 3}; // อาร์เรย์ที่กำหนด
    int k = 3;
    int size = sizeof(arr) / sizeof(arr[0]); // ขนาดอาร์เรย์
    int answer = 0; // ตัวนับคำตอบ
    build(arr, 1, 0, size - 1); // สร้าง Segment Tree
    
    for(int i = 0; i < size; i++) {
        int start = i, end = size-1;
        int ind = INT_MAX;
        while(start <= end) { // Binary Search
            int mid = (start + end) / 2;
            if(query(1, 0, size-1, i, mid) >= k) { // ตรวจสอบซับอาร์เรย์
                ind = min(mid, ind);
                end = mid - 1;
            } else
                start = mid + 1;
        }
        if(ind != INT_MAX) // หาก ind เปลี่ยนแปลง ให้เพิ่มคำตอบ
            answer += size - ind;
    }
    cout << answer << "\n";
    return 0;
}

ผลลัพธ์

4

ในวิธีนี้ เราใช้ Binary Search และ Segment Tree ซึ่งช่วยลดความซับซ้อนด้านเวลาจาก O(N²) เป็น O(N log N) ซึ่งดีมาก โปรแกรมนี้จึงทำงานได้กับข้อจำกัดขนาดใหญ่ ไม่เหมือนวิธีก่อนหน้า

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนซับอาร์เรย์ที่มี OR ≥ K ด้วยความซับซ้อนด้านเวลา O(n log n) โดยใช้ Binary Search และ Segment Tree เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งแบบปกติและแบบมีประสิทธิภาพ สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน หวังว่าบทความนี้จะเป็นประโยชน์