Tulis kod dalam C++ untuk mencari bilangan subarray dengan bit atau nilai lebih besar daripada atau sama dengan K

Dalam artikel ini, kami akan menerangkan secara ringkas cara menyelesaikan bilangan subarray dengan bitwise OR>=K dalam C++. Jadi kita mempunyai array arr[] dan integer K, dan kita perlu mencari bilangan subarray yang OR (bitwise OR) lebih besar daripada atau sama dengan K. Jadi inilah contoh masalah yang diberikan -

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

Cara untuk mencari penyelesaian

Sekarang kita akan menggunakan dua kaedah berbeza untuk menyelesaikan masalah menggunakan C++ -

Brute force

Dalam kaedah ini kita hanya akan Lelaran ke atas semua subarray yang boleh dibentuk dan semak sama ada OR lebih besar daripada atau sama dengan K. Jika ya, maka kami akan menambah jawapan kami. . N *N)

, dengan N ialah saiz tatasusunan yang diberikan, jadi sekarang kita akan menggunakan kaedah yang cekap.

Kaedah yang cekap

Dalam kaedah ini kita akan menggunakan beberapa sifat operator OR iaitu walaupun kita menambah lebih banyak nombor ia tidak akan berkurangan jadi jika kita mendapat sub tatasusunan daripada i ke j ORnya lebih besar daripada atau sama dengan K, maka setiap subarray yang mengandungi julat {i,j} akan mempunyai ATAU lebih besar daripada K. Kami memanfaatkan sifat ini dan memperbaik kod kami.

Contoh

#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

Dalam kaedah ini, kami menggunakan carian binari dan pokok segmen, yang membantu mengurangkan kerumitan masa daripada

O(N*N) kepada O(Nlog(N))

, ini sangat bagus . Kini, tidak seperti prosedur sebelumnya, prosedur ini juga boleh digunakan untuk kekangan yang lebih besar.

Kesimpulan

Dalam artikel ini kami menyelesaikan masalah untuk mencari bilangan subarray dengan OR >= K menggunakan

pencarian binari dan pokok segmen dengan kerumitan masa O(nlog(n)). Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan cara lengkap untuk menyelesaikan masalah ini (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Semoga artikel ini bermanfaat kepada anda.

Atas ialah kandungan terperinci Tulis kod dalam C++ untuk mencari bilangan subarray dengan bit atau nilai lebih besar daripada atau sama dengan K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!