이 기사에서는 C++에서 비트 단위 OR>=K가 있는 하위 배열의 수를 해결하는 방법에 대해 간략하게 설명합니다. 그래서 배열 arr[]와 정수 K가 있고 OR(bitwise or)이 K보다 크거나 같은 하위 배열의 수를 찾아야 합니다. 그래서 여기에 주어진 문제의 예가 있습니다 -
Input: arr[] = {1, 2, 3} K = 3
Output: 4
Bitwise OR of sub-arrays:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 sub-arrays have bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6
Output: 2 해결책을 찾기 위한 접근 방식
이제 우리는 C++를 사용하여 문제를 해결하기 위해 두 가지 다른 방법을 사용할 것입니다 -
브루트 포스
이 접근 방식에서 우리는 단순히 형성할 수 있는 모든 하위 배열을 살펴보고 OR이 K보다 크거나 같은지 확인할 것입니다. 그렇다면 우리는 우리의 대답을 증가시킬 것입니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 2, 3}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(int); // the size of our array.
int answer = 0; // the counter variable.
for(int i = 0; i < size; i++){
int bitwise = 0; // the variable that we compare to k.
for(int j = i; j < size; j++){ // all the subarrays starting from i.
bitwise = bitwise | arr[j];
if(bitwise >= k) // if bitwise >= k increment answer.
answer++;
}
}
cout << answer << "\n";
return 0;
} 출력
4
이 접근 방식은 매우 간단하지만 이 접근 방식은 더 높은 제약 조건과 마찬가지로 더 높은 제약 조건에 적합하지 않기 때문에 결점이 있습니다. 이 접근 방식의 시간 복잡성이 O(N*N)이므로 시간이 너무 많이 걸립니다. 여기서 N은 주어진 배열의 크기이므로 이제 효율적인 접근 방식을 사용합니다.
효율적인 접근
이 접근 방식에서 우리는 OR 연산자의 몇 가지 속성을 사용할 것입니다. 즉, 더 많은 숫자를 추가하더라도 절대 감소하지 않습니다. 범위 {i,j}를 포함하는 하위 배열은 K보다 많은 OR을 가지며 우리는 이 속성을 활용하여 코드를 개선합니다.
예시
#include <bits/stdc++.h>
#define N 1000
using namespace std;
int t[4*N];
void build(int* a, int v, int start, int end){ // segment tree building
if(start == end){
t[v] = a[start];
return;
}
int mid = (start + end)/2;
build(a, 2 * v, start, mid);
build(a, 2 * v + 1, mid + 1, end);
t[v] = t[2 * v] | t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r){ // for processing our queries or subarrays.
if (l > r)
return 0;
if(tl == l && tr == r)
return t[v];
int tm = (tl + tr)/2;
int q1 = query(2*v, tl, tm, l, min(tm, r));
int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
return q1 | q2;
}
int main(){
int arr[] = {1, 2, 3}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(arr[0]); // the size of our array.
int answer = 0; // the counter variable.
build(arr, 1, 0, size - 1); // building segment tree.
for(int i = 0; i < size; i++){
int start = i, end = size-1;
int ind = INT_MAX;
while(start <= end){ // binary search
int mid = (start + end) / 2;
if(query(1, 0, size-1, i, mid) >= k){ // checking subarray.
ind = min(mid, ind);
end = mid - 1;
}
else
start = mid + 1;
}
if(ind != INT_MAX) // if ind is changed then increment the answer.
answer += size - ind;
}
cout << answer << "\n";
return 0;
} 출력
4
이 접근 방식에서는 이진 검색 및 세그먼트 트리를 사용하여 시간 복잡성을 O(N*N)에서 O(Nlog(N))으로 줄이는 데 도움이 됩니다. , 아주 좋은 것입니다. 이제 이 프로그램은 이전 프로그램과 달리 더 큰 제약 조건에서도 작동할 수 있습니다.
결론
이 기사에서는 이진 검색 및 세그먼트 트리를 사용하여 O(nlog(n)) 시간 복잡도에서 OR>=K를 갖는 하위 배열의 수를 찾는 문제를 해결합니다. . 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.