C ++中最接近K的子数组的按位与

在这个问题中，我们得到了大小为n且整数为k的数组arr []。我们的任务是在索引i到j之间找到子数组，并计算所有元素的按位与。在此打印之后，最小值为abs（K-（子数组的按位与）。

让我们举个例子来了解这个问题，

输入− arr [] = {5，1}，k = 2

输出-

为了解决这个问题，可以有几种方法。

一种简单的解决方案是使用直接方法。通过找到所有子数组的按位与，然后找到| KX |。

步骤1-找到所有子数组的按位与。

步骤2-对于从上述步骤1中找到的每个值（例如X）。找到| k-X |的值。

步骤3-将上面找到的最小值存储在min变量中。

步骤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