Trong bài viết này, chúng tôi đã đưa ra một vấn đề trong đó chúng tôi được cung cấp một mảng các số nguyên và chúng tôi có nhiệm vụ tìm AND bitwise của các dải ô đã cho, ví dụ 7minus;
Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}
Output:
1
0 0
1 AND 31 = 1
23 AND 34 AND 4 = 00
Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}
Output:
0 8
0 Trước tiên, chúng tôi sẽ áp dụng phương pháp vũ phu và kiểm tra độ phức tạp về thời gian của nó. Nếu mức độ phức tạp về thời gian của chúng tôi không đủ tốt, chúng tôi sẽ cố gắng phát triển một cách tiếp cận tốt hơn.
Phương pháp tiếp cận vũ phu
Trong cách tiếp cận đã cho, chúng tôi sẽ đi qua phạm vi nhất định và tìm câu trả lời của chúng tôi và in nó.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main() {
int ARR[] = { 10, 10 , 12, 16, 8 };
int n = sizeof(ARR) / sizeof(int); // size of our array
int queries[][2] = { {0, 2}, {3, 4} }; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for(int i = 0; i < q; i++) { // traversing through all the queries
long ans = 1LL << 32;
ans -= 1; // making all the bits of ans 1
for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
ans &= ARR[j]; // calculating the answer
cout << ans << "\n";
}
return 0;
} Đầu ra
8 0
Trong cách tiếp cận này, chúng tôi chạy một vòng lặp qua các phạm vi của từng truy vấn và in bitwise chung của chúng, VÀ do đó, độ phức tạp tổng thể của chương trình của chúng tôi trở thành O (N * Q) , trong đó N là kích thước mảng của chúng ta và Q là số lượng truy vấn của chúng ta hiện tại vì bạn có thể thấy độ phức tạp này không phù hợp với các ràng buộc cao hơn, vì vậy chúng tôi sẽ đưa ra cách tiếp cận nhanh hơn cho vấn đề này.
Phương pháp tiếp cận hiệu quả
Trong bài toán này, chúng tôi tính toán trước số bit tiền tố của mảng để tính theo chiều bit AND của dải ô đã cho bằng cách kiểm tra sự đóng góp của các bit đã đặt trong dải ô đã cho.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];
void bitcount(int *ARR, int n) { // making prefix counts
for (int j = 31; j >= 0; j--) {
prefixbits[j][0] = ((ARR[0] >> j) & 1);
for (int i = 1; i < n; i++) {
prefixbits[j][i] = ARR[i] & (1LL << j);
prefixbits[j][i] += prefixbits[j][i - 1];
}
}
return;
}
int check(int l, int r) { // calculating the answer
long ans = 0; // to avoid overflow we are taking ans as long
for (int i = 0; i < 32; i++){
int x;
if (l == 0)
x = prefixbits[i][r];
else
x = prefixbits[i][r] - prefixbits[i][l - 1];
if (x == r - l + 1)
ans = ans | 1LL << i;
}
return ans;
}
int main() {
int ARR[] = { 10, 10 , 12, 16, 8 };
int n = sizeof(ARR) / sizeof(int); // size of our array
memset(prefixbits, 0, sizeof(prefixbits)); // initializing all the elements with 0
bitcount(ARR, n);
int queries[][2] = {{0, 2}, {3, 4}}; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
cout << check(queries[i][0], queries[i][1]) << "\n";
}
return 0;
} Đầu ra
2 0
Trong cách tiếp cận này, chúng tôi đang dành một khoảng thời gian cố định để tính toán các truy vấn làm giảm đáng kể độ phức tạp về thời gian của chúng tôi từ O (N * Q) thành O (N) , trong đó N là kích thước của mảng đã cho của chúng ta bây giờ. Chương trình này cũng có thể hoạt động đối với các ràng buộc cao hơn.
Giải thích về đoạn mã trên
Với cách tiếp cận này, chúng tôi đang tính toán tất cả các số bit tiền tố và lưu trữ nó trong chỉ mục. Bây giờ khi chúng ta tính toán các truy vấn, chúng ta chỉ cần kiểm tra xem một bit có cùng số lượng với số phần tử có trong phạm vi hay không. Nếu có, chúng tôi đặt bit này thành 1 trong x của chúng tôi và nếu không, chúng tôi để lại bit như thể bất kỳ số nào có mặt trong phạm vi đã cho có bit 0 đó, vì vậy toàn bộ bitwise AND của bit đó sẽ bằng 0, và đó là cách chúng tôi đang tính toán bitwise AND.
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để liệt kê tất cả các truy vấn cho bitwise AND trong phạm vi chỉ số [L, R] của mảng đã cho. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.