C++를 사용하여 K보다 크거나 같은 비트 또는 값을 갖는 하위 배열의 수를 찾는 코드를 작성하세요.

이 기사에서는 C++에서 비트별 OR>=K를 사용하여 하위 배열 수를 구하는 방법을 간략하게 설명합니다. 따라서 배열 arr[]과 정수 K가 있고 OR(비트별 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보다 크거나 같은지 확인합니다. 그렇다면 답변을 추가하겠습니다.

Example

#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;
}

Output

4

이 방법은 매우 간단하지만 단점이 있습니다. 왜냐하면 이 방법은 더 높은 제약 조건에 적합하지 않고 더 높은 제약 조건에 대해서는 너무 많은 시간이 걸리기 때문입니다. 이 방법의 시간 복잡도는 O( N *N), 여기서 N은 주어진 배열의 크기이므로 이제 효율적인 방법을 사용하겠습니다.

효율적인 방법

이 방법에서는 OR 연산자의 일부 속성을 사용합니다. 즉, 더 많은 숫자를 추가하더라도 숫자는 줄어들지 않으므로 i에서 j까지 하위 배열을 가져오면 해당 OR은 K보다 크거나 같습니다. {i,j} 범위를 포함하는 각 하위 배열은 K보다 큰 OR을 갖습니다. 우리는 이 속성을 활용하여 코드를 개선하고 있습니다.

Example

#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;
}

Output

4

이 방법에서는 이진 검색과 세그먼트 트리를 사용하여 시간 복잡도를 O(N*N)에서 O(Nlog(N))으로 줄이는 데 도움이 됩니다. 이는 매우 좋습니다. . 이제 이전 절차와 달리 이 절차는 더 큰 제약 조건에도 적용될 수 있습니다.

결론

이 기사에서는 시간 복잡도가 O(nlog(n))인 이진 검색 및 세그먼트 트리를 사용하여 OR >= K인 하위 배열 수를 찾는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 K보다 크거나 같은 비트 또는 값을 갖는 하위 배열의 수를 찾는 코드를 작성하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!