Trong bài viết này, chúng tôi sẽ cung cấp một lời giải thích ngắn gọn về việc giải quyết số lượng các mảng con có bitwise OR> =K trong C ++. Vì vậy, chúng ta có một mảng arr [] và một số nguyên K, và chúng ta phải tìm số mảng con có OR (theo chiều bit hoặc) lớn hơn hoặc bằng K. Vì vậy, đây là ví dụ của bài toán đã cho -
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 Phương pháp tiếp cận để tìm giải pháp
Bây giờ chúng ta sẽ sử dụng hai phương pháp khác nhau để giải quyết vấn đề bằng C ++ -
Lực lượng vũ phu
Trong cách tiếp cận này, chúng ta chỉ đơn giản là sẽ đi qua tất cả các mảng con có thể được hình thành và kiểm tra xem OR có lớn hơn hoặc bằng K hay không. Nếu có, thì chúng tôi sẽ tăng câu trả lời của mình.
Ví dụ
#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;
} Đầu ra
4
Cách tiếp cận này rất đơn giản, nhưng nó có những khiếm khuyết vì cách tiếp cận này không tốt cho các ràng buộc cao hơn vì đối với các ràng buộc cao hơn, nó sẽ mất quá nhiều thời gian vì độ phức tạp về thời gian của phương pháp này là O (N * N) trong đó N là kích thước của mảng đã cho, vì vậy bây giờ chúng ta sẽ tìm một cách tiếp cận hiệu quả.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng ta sẽ sử dụng một số thuộc tính của toán tử OR, đó là nó không bao giờ giảm ngay cả khi chúng ta thêm nhiều số hơn, vì vậy nếu chúng ta nhận được một mảng con từ i đến j có OR lớn hơn hoặc bằng K, vì vậy mọi mảng con bao gồm dải ô {i, j} sẽ có HOẶC nhiều hơn K và chúng tôi đang tận dụng thuộc tính này và cải thiện mã của mình.
Ví dụ
#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;
} Đầu ra
4
Trong cách tiếp cận này, chúng tôi đang sử dụng tìm kiếm nhị phân và cây phân đoạn, giúp giảm độ phức tạp về thời gian của chúng tôi từ O (N * N) xuống O (Nlog (N)) , điều đó rất tốt. Giờ đây, chương trình này cũng có thể hoạt động đối với các ràng buộc lớn hơn, không giống như chương trình trước đó.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề để tìm Số lượng mảng con có OR> =K theo độ phức tạp thời gian O (nlog (n)) bằng cách sử dụng Tìm kiếm nhị phân và cây phân đoạn . Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.