C++에서 K에 가장 가까운 하위 배열의 비트 AND

이 문제에서는 크기가 n이고 정수 k인 배열 arr[]이 제공됩니다. 우리의 임무는 인덱스 i에서 j까지의 하위 배열을 찾고 모든 요소의 비트 AND를 계산하는 것입니다. 이 후 abs(K-(하위 배열의 비트 AND))의 최소값을 인쇄합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 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