이 기사에서 우리는 정수 배열이 주어지는 문제를 제시했고 주어진 범위의 비트 AND를 찾는 임무를 받았습니다(예: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 먼저 무차별 대입 접근 방식을 적용하고 시간 복잡도를 확인합니다. 시간 복잡도가 충분하지 않다면 더 나은 접근 방식을 개발하기 위해 노력할 것입니다.
무차별 대입 접근
주어진 접근 방식에서 우리는 주어진 범위를 탐색하고 답을 찾아 인쇄합니다.
예시
#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;
} 출력
8 0
이 접근 방식에서 우리는 각 쿼리의 범위를 통해 루프를 실행하고 집합적인 비트 단위로 인쇄하므로 프로그램의 전체 복잡성은 O(N*Q)가 됩니다. , 여기서 N은 배열의 크기이고 Q는 쿼리 수입니다. 이 복잡성은 더 높은 제약 조건에 적합하지 않으므로 이 문제에 대한 더 빠른 접근 방식을 제시할 것입니다.
효율적인 접근
이 문제에서는 배열의 접두사 비트 수를 미리 계산하여 주어진 범위에서 설정된 비트의 기여도를 확인하여 주어진 범위의 비트 AND를 계산합니다.
예시
#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;
} 출력
2 0
이 접근 방식에서는 O(N*Q)에서 시간 복잡성을 상당히 줄이는 쿼리를 계산하는 데 일정한 시간을 할애하고 있습니다. O(N)으로 , 여기서 N은 주어진 배열의 크기입니다. 이 프로그램은 더 높은 제약 조건에서도 작동할 수 있습니다.
위 코드 설명
이 접근 방식에서는 모든 접두사 비트 수를 계산하여 인덱스에 저장합니다. 이제 쿼리를 계산할 때 범위에 있는 요소 수와 비트 수가 동일한지 여부만 확인하면 됩니다. 예인 경우 x에서 이 비트를 1로 설정하고, 아니오인 경우 주어진 범위에 있는 임의의 숫자에 해당 비트 0이 있는 것처럼 비트를 그대로 둡니다. 따라서 해당 비트의 전체 비트 AND는 0이 됩니다. 비트 AND를 계산하고 있습니다.
결론
이 기사에서는 주어진 배열의 인덱스 범위 [L, R]에서 비트 AND에 대한 모든 쿼리를 열거하는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.