Bitwise AND ของ Sub-array ที่ใกล้เคียง K มากที่สุดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และจำนวนเต็ม k ภารกิจคือการหา subarray จากดัชนี i ถึง j และคำนวณ bitwise AND ขององค์ประกอบทั้งหมดของมัน หลังจากนั้นพิมพ์ค่าต่ำสุดของ abs(K - (bitwise AND ของ subarray))

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต − arr[] = {5, 1}, k = 2

เอาต์พุต −

เพื่อแก้ปัญหานี้ สามารถมีหลายวิธี

วิธีง่ายหนึ่งคือใช้วิธีโดยตรง โดยหา bitwise AND สำหรับ sub-array ทุกตัว แล้วหา |K-X|

ขั้นตอน 1 − หา bitwise AND สำหรับ sub-array ทุกตัว

ขั้นตอน 2 − สำหรับแต่ละค่าที่ได้จากขั้นตอน 1 (ให้เป็น X) หาค่า |k - X|

ขั้นตอน 3 − เก็บค่าต่ำสุดที่พบไว้ในตัวแปร min

ขั้นตอน 4 − ท้ายสุด พิมพ์ min

ตัวอย่างโปรแกรม (วิธีแบบง่าย)

#include <iostream>
using namespace std;

int CalcBitwiseANDClosestK(int arr[], int n, int k) {
    int minimum = 1000;
    for (int i = 0; i < n; i++) {
        int X = arr[i];
        for (int j = i; j < n; j++) {
            X &= arr[j];
            minimum = min(minimum, abs(k - X));
        }
    }
    return minimum;
}

int main() {
    int arr[] = { 1, 6, 4, 9, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << "Minimum value difference between Bitwise AND of sub-array and K is " << CalcBitwiseANDClosestK(arr, n, k);
    return 0;
}

เอาต์พุต

Minimum value difference between Bitwise AND of sub-array and K is 1

วิธีแก้อีกวิธีคือการสังเกตการทำงานของ AND ใน sub-array การทำ bitwise AND จะไม่มีค่าเพิ่มขึ้นเลย ดังนั้นเราต้องตรวจสอบความต่างต่ำสุดซึ่งจะเพิ่มขึ้นเมื่อ X ≤ K

ตัวอย่างโปรแกรม (วิธีปรับปรุง)

#include <iostream>
using namespace std;

int CalcBitwiseANDClosestK(int arr[], int n, int k) {
    int minimum = 1000000;
    for (int i = 0; i < n; i++) {
        int BitwiseAND = arr[i];
        for (int j = i; j < n; j++) {
            BitwiseAND &= arr[j];
            minimum = min(minimum, abs(k - BitwiseAND));
            if (BitwiseAND <= k)
                break;
        }
    }
    return minimum;
}

int main() {
    int arr[] = {1, 6, 4, 9, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << "Minimum value difference between Bitwise AND of sub-array and K is " << CalcBitwiseANDClosestK(arr, n, k);
    return 0;
}

เอาต์พุต

Minimum value difference between Bitwise AND of sub-array and K is 1