Trong bài toán này, ta được cho mảng arr[] kích thước n và số nguyên k. Nhiệm vụ: tìm mảng con từ chỉ số i đến j và tính bitwise AND của tất cả phần tử. In ra giá trị nhỏ nhất của |K - (bitwise AND của mảng con)|.
Ví dụ minh họa
Đầu vào** – arr[] = {5, 1}, k = 2
Đầu ra** –
Các phương pháp giải:
Cách đơn giản: tìm bitwise AND cho mọi mảng con, rồi tìm min |K - X|.
Bước 1** – Tìm bitwise AND tất cả mảng con.
Bước 2** – Với mỗi giá trị X tìm được, tính |K - X|.
Bước 3** – Lưu giá trị nhỏ nhất.
Bước 4** – In kết quả.
Ví dụ
#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
Cách tối ưu hơn: nhận thấy bitwise AND của mảng con không bao giờ tăng khi mở rộng mảng con. Nếu X ≤ K thì hiệu |K-X| sẽ tăng, có thể dừng sớm.
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