Nhận xét

• OR chỉ bật thêm bit ~1~, không bao giờ tắt bit đã có Khi bạn OR một tập các số, mọi bit 1 của từng số đều được giữ lại, và chỉ có thể "mở" thêm các bit ~1~ mới từ các số đó.

• Hệ quả: Để tạo ra một số ~x~ bằng OR của một tập con của ~A~, thì:

  • Mỗi bit 1 của ~x~ phải có ít nhất một số trong tập con đó cũng có bit 1 ở vị trí tương ứng (để "bật" bit này).
  • Không thể tắt bất kỳ bit ~1~ không mong muốn nào: nếu bạn chọn một số có thêm bit ~1~ ngoài những bit của ~x~, kết quả OR sẽ bật luôn những bit đó và vượt quá ~x~.

• Theo đó, nếu trong mảng ~A~ hoàn toàn không có bất kỳ số nào bật bit ~k~ (tức không có số nào có ~2^k~ trong thành phần nhị phân), thì bạn không thể tạo ra bất kỳ số ~x~ nào có bit ~k = 1~.

Chính vì thế,ta có thể nhận thấy số dương nhỏ nhất không thể biểu diễn được chính là lũy thừa của ~2~ nhỏ nhất mà ~A~ không chứa.

Để chặt chẽ hơn, ta sẽ chứng minh rằng:

Số dương nhỏ nhất không thân thiện với ~A~ là ~2^k~, trong đó ~k~ là số mũ nhỏ nhất sao cho không tồn tại ~A_i = 2^k~.

Chứng minh phản chứng

Giả sử ~x~ là số dương nhỏ nhất không thân thiện với ~A~, nhưng ~x~ không phải là lũy thừa của ~2~.

Vì ~x~ không phải lũy thừa của ~2~, trong biểu diễn nhị phân của ~x~ có ít nhất hai bit 1. Ta viết

$$ x \;=\; a\;+\;b, $$

trong đó

• ~a~ chỉ lấy các bit ~1~ tách ra phần thấp hơn,
• ~b~ chỉ lấy các bit ~1~ tách ra phần cao hơn,
• Thỏa mãn ~0 < a < x~, ~0 < b < x~, và ~a~ với ~b~ không cùng bật bit nào (hai nhị phân của ~a~ và ~b~ không chồng chéo bit 1).

Ví dụ: nếu ~x = 13 = 1101_2~, ta có thể chọn ~a=5=0101_2~, ~b=8=1000_2~.

• Vì ~a < x~ và ~b < x~ và ~x~ là số nhỏ nhất không thân thiện, nên cả ~a~ và ~b~ đều thân thiện với ~A~ (vì nếu ~a~ hoặc ~b~ mà không thân thiện mà ~a < x~ và ~b < x~ dẫn đến ~x~ không còn là số nhỏ nhất nữa).

  • Tức là có một dãy chỉ số ~i_1<\cdots<i_p~ sao cho</p>

    $$ A_{i_1}\;\bigl|\;\cdots\;\bigl|\;A_{i_p} \;=\; a $$

  • Và có một dãy chỉ số ~j_1<\cdots<j_q~ sao cho</p>

    $$ A_{j_1}\;\bigl|\;\cdots\;\bigl|\;A_{j_q} \;=\; b $$

• Vì ~a~ và ~b~ bật các bit ~1~ ở các vị trí khác nhau, khi ta lấy hợp ~\{i_1,\dots,i_p\}\cup\{j_1,\dots,j_q\}~ (sắp theo thứ tự tăng) thì

$$ \Bigl(A_{i_1}\;\bigl|\;\cdots\;\bigl|\;A_{i_p}\Bigr) \;\bigl|\; \Bigl(A_{j_1}\;\bigl|\;\cdots\;\bigl|\;A_{j_q}\Bigr) \;=\; a\;\bigl|\;b \;=\; x. $$

Và vì trong các chỉ số ~i~ với ~j~ không có xung đột (chúng ta chỉ cần sắp lại hai dãy con cho thành một dãy con tăng), nên ~x~ có thể được biểu diễn dưới dạng OR của một tập con của ~A~.

~\longrightarrow~ Điều này mâu thuẫn với giả thiết "~x~ không thân thiện"

Phản chứng trên cho thấy không tồn tại số ~x~ nhỏ nhất không thân thiện mà không phải lũy thừa của 2.

~\Longrightarrow~ Vậy số dương nhỏ nhất không thân thiện với ~A~ phải là một lũy thừa của ~2~, tức ~x \;=\; 2^k~ với ~k~ là chỉ số nhỏ nhất sao cho không có ~A_i = 2^k~.

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

void sol(){
    int n; cin >> n;
    vector <int> a(n);
    for(int &x : a) cin >> x;
    unordered_set<int> s;
    for (int x : a) if ((x & (x - 1)) == 0) s.insert(x);
    int ans = 1;
    while (s.count(ans)) ans <<= 1;
    cout << ans << "\n";
}

int main(){
    int t; cin >> t;
    while(t--) sol();
}