Bitwise AND của mảng con gần nhất với K trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n và một số nguyên k. Nhiệm vụ của chúng ta là tìm mảng con trong phạm vi từ chỉ mục i đến j và tính toán theo từng bit AND của tất cả các phần tử của nó. Sau giá trị tối thiểu in này là abs (K- (bitwise AND của mảng con)).

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - arr [] ={5, 1}, k =2

Đầu ra -

Để giải quyết vấn đề, có thể có một số phương pháp.

Một giải pháp đơn giản sẽ là sử dụng phương pháp trực tiếp. Bằng cách tìm bitwise AND cho tất cả các mảng con, sau đó tìm | K-X |.

Bước 1 - Tìm bitwise AND cho tất cả các mảng con.

Bước 2 - Với mỗi giá trị tìm được từ bước 1 ở trên (giả sử X). Tìm giá trị của | k - X |.

Bước 3 - Lưu trữ giá trị nhỏ nhất được tìm thấy ở trên trong một biến tối thiểu.

Bước 4 - Ở cuối, in min.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

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

Một giải pháp khác có thể là sử dụng quan sát hoạt động AND trong mảng con. Bitwise AND có một đặc điểm là nó sẽ không bao giờ tăng. Vì vậy, chúng ta phải kiểm tra sự khác biệt tối thiểu sẽ tăng lên khi X ≤ K.

Ví dụ

#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;
}

Đầu ra

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