Để giải quyết vấn đề trong đó chúng ta được cung cấp một mảng và chúng ta cần tìm tất cả các số nguyên có thể có là bitwise VÀ của ít nhất một mảng con không trống, chẳng hạn -
Input : nums[ ] = { 3, 5, 1, 2, 8 }
Output : { 2, 5, 0, 3, 8, 1 }
Explanation:
2 is the bitwise AND of subarray {2},
5 is the bitwise AND of subarray {5},
0 is the bitwise AND of subarray {1, 2}, {2, 8} and {1, 2, 8},
3 is the bitwise AND of subarray {3},
8 is the bitwise AND of subarray {8},
1 is the bitwise AND of subarray {1}, {3, 5} and {3, 5, 1}.
Input : nums[ ] = { 2, 6, 3, 8, 1 }
Output: { 1, 8, 3, 6, 2, 0 } Phương pháp tiếp cận để tìm giải pháp
A Phương pháp tiếp cận đơn giản có thể được áp dụng là,
-
Tìm tất cả các mảng con không trống có thể có.
-
Trong khi duyệt qua mảng, hãy tính toán theo từng bit AND của mỗi phần tử trong mảng con.
-
Để tránh các giá trị trùng lặp, hãy lưu trữ tất cả các kết quả trong một tập hợp.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] ={ 2, 6, 3, 8, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
// Declaring set to store result of each AND operation.
unordered_set<int> result;
int val;
// nested loops to traverse through all the possible non empty subarrays.
for (int i = 0; i < n; ++i){
for (int j = i, val = INT_MAX; j < n; ++j){
val = val & arr[j];
// storing result of AND operation
result.insert(val);
}
}
cout << "All possible numbers are: ";
// printing all the values of set.
for (auto i = result.begin(); i != result.end();i++)
cout << *i << " ";
return 0;
} Đầu ra
All possible numbers are: 1 8 3 6 0 2
Giải thích về Quy tắc trên
-
Khai báo tập hợp để lưu trữ tất cả các kết quả của phép toán AND.
-
Khởi tạo biến ‘val’ bằng INT_MAX vì chúng ta cần thực hiện thao tác AND với tất cả các bit được đặt thành 1.
-
Vòng lặp bên trong để đi qua tất cả các mảng con có thể có từ chỉ mục thứ i.
-
Tính toán hoạt động AND của từng phần tử với nhau và với chính chúng và lưu trữ trong tập kết quả.
-
In tất cả các giá trị của tập kết quả.
Kết luận
Trong hướng dẫn này, Chúng tôi đã thảo luận về một cách tiếp cận đơn giản để giải quyết vấn đề này, tức là, tính toán hoạt động AND trong mọi mảng con có thể có. Chúng tôi cũng đã thảo luận về chương trình C ++ để giải quyết vấn đề này. Ngoài ra, bạn có thể viết mã này bằng bất kỳ ngôn ngữ nào khác như Java, C, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.