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)

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

4

Salin selepas log masuk

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.

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!