Bitwise AND ของอาร์เรย์ย่อยที่ใกล้เคียงที่สุดกับ K ใน C++

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − arr[] ={5, 1}, k =2

ผลผลิต −

ในการแก้ปัญหานั้น สามารถทำได้หลายวิธี

วิธีแก้ไขง่ายๆ วิธีหนึ่งคือใช้วิธีการโดยตรง โดยการค้นหาระดับบิต AND สำหรับอาร์เรย์ย่อยทั้งหมด จากนั้นจึงค้นหา |K-X|.

ขั้นตอนที่ 1 − ค้นหาระดับบิต AND สำหรับอาร์เรย์ย่อยทั้งหมด

ขั้นตอนที่ 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 ในอาร์เรย์ย่อย ระดับบิต 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