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