C++でKに最も近いサブ配列のビットごとのAND

この問題では、サイズnと整数kの配列arr[]が与えられます。私たちのタスクは、インデックスiからjまでのサブ配列を見つけて、そのすべての要素のビットごとのANDを計算することです。この後、abs（K-（サブ配列のビットごとのAND））の最小値を出力します。

問題を理解するために例を見てみましょう

入力 − arr [] ={5、1}、k =2

出力 −

この問題を解決するには、いくつかの方法があります。

簡単な解決策の1つは、直接法を使用することです。すべてのサブ配列のビットごとのANDを見つけてから、|K-X|を見つけます。

ステップ1 −すべてのサブ配列のビットごとのANDを見つけます。

ステップ2 −上記のステップ1で見つかった値ごとに（たとえばX）。 | k--X|の値を見つけます。

ステップ3 −上記の最小値を最小変数に格納します。

ステップ4 −最後に、分を印刷します。

例

ソリューションの動作を説明するプログラム

#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