C++ Các số là AND bitwise của ít nhất một mảng con không rỗng

Cho mảng, tìm tất cả số nguyên là AND bitwise của ít nhất một mảng con không rỗng. Ví dụ:

Input: {3,5,1,2,8} → Output: {2,5,0,3,8,1}
Giải thích: 2=AND{2}, 5=AND{5}, 0=AND{1,2},{2,8},{1,2,8}, 3=AND{3}, 8=AND{8}, 1=AND{1},{3,5},{3,5,1}

Phương pháp đơn giản

Sinh tất cả mảng con, tính AND từng mảng con, lưu vào set tránh trùng. Độ phức tạp O(n²).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {2,6,3,8,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    unordered_set<int> result;

    for (int i=0; i<n; i++) {
        int val = INT_MAX;
        for (int j=i; j<n; j++) {
            val &= arr[j];
            result.insert(val);
        }
    }

    cout << "Tất cả số có thể: ";
    for (int x: result) cout << x << " ";
    return 0;
}

Kết quả

Tất cả số có thể: 1 8 3 6 0 2

Giải thích

• Khởi tạo val = INT_MAX (tất cả bit = 1).
• Vòng lặp lồng: i = chỉ số bắt đầu, j = chỉ số kết thúc mảng con.
• Cập nhật val &= arr[j], insert vào set.

Kết luận

Đã trình bày phương pháp đơn giản O(n²) tìm tất cả giá trị AND của mảng con. Code C++ chuyển được sang Java, Python, C. Hy vọng hữu ích.