Tìm N số riêng biệt có OR bitwise bằng K trong Python

Cho hai số nguyên N và K, tìm N giá trị duy nhất sao cho phép OR bitwise của chúng bằng K. Nếu không tồn tại, trả về -1.

Ví dụ: N = 4, K = 6 → Kết quả: [6, 0, 1, 2] vì 6|0|1|2 = 6.

Thuật toán

1. Dùng mảng visited kích thước 32 để đánh dấu bit đã dùng.
2. Hàm add(num) tạo số từ các bit chưa dùng dựa trên num.
3. Đếm số bit 1 trong K (cnt_k). Số tập con có thể tạo = 2^cnt_k.
4. Nếu 2^cnt_k < N → trả về -1.
5. Thêm K vào kết quả, sau đó sinh N-1 số còn lại bằng cách duyệt i từ 0 đến 2^cnt_k - 1, gọi add(i).

Ví dụ code

MAX = 32
visited = [False] * MAX
res = []

def set_bit_count(n):
    if n == 0:
        return 0
    return (n & 1) + set_bit_count(n >> 1)

def add(num):
    point = 0
    value = 0
    for i in range(MAX):
        if visited[i]:
            continue
        if num & 1:
            value += (1 << i)
        num //= 2
    res.append(value)

def solve(n, k):
    pow2 = [2**i for i in range(MAX)]
    res.append(k)
    cnt_k = set_bit_count(k)
    if pow2[cnt_k] < n:
        return -1
    count = 0
    for i in range(pow2[cnt_k] - 1):
        add(i)
        count += 1
        if count == n:
            break
    return res

n = 4
k = 6
print(solve(n, k))

Input

4, 6

Output

[6, 0, 1, 2]