หา N จำนวนที่ต่างกันซึ่ง Bitwise OR เท่ากับ K ใน Python

โจทย์: กำหนด N และ K หา N จำนวนที่ไม่ซ้ำกัน ที่ bitwise OR ของทั้งหมดเท่ากับ K ถ้าไม่ได้ → คืน -1

ตัวอย่าง: N=4, K=6 (binary 110) → [6, 0, 1, 2] เพราะ 6|0|1|2 = 6

อัลกอริทึม

1. นับจำนวนบิต 1 ใน K (cnt_k)
2. จำนวนชุดย่อยของบิต 1 = 2^cnt_k ต้อง ≥ N ไม่งั้น impossible
3. สร้างตัวเลขจากชุดย่อยของบิตที่เป็น 1 ใน K (ใช้ visited array กันซ้ำ)
4. ใส่ K เองเป็นตัวแรก แล้วเติมจากชุดย่อยจนครบ N ตัว

ตัวอย่างโค้ด

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):
    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

print(solve(4, 6))  # [6, 0, 1, 2]

ผลลัพธ์

[6, 0, 1, 2]

สรุป: ใช้คุณสมบัติ bitwise OR: ผลลัพธ์มีบิต 1 เฉพาะตำแหน่งที่ K มีบิต 1 → ตัวเลขที่ใช้ได้ต้องเป็นชุดย่อยของบิต 1 ใน K