ข้อ 69 · LC1318 Minimum Flips to Make a OR b Equal to c (พลิกบิตน้อยสุด) 🟡

โจทย์ (LC1318): กำหนดจำนวนเต็มบวกสามตัว a, b และ c ให้หาจำนวนครั้งน้อยที่สุดที่ต้องพลิก (flip) bit ของ a และ b รวมกัน เพื่อให้ (a OR b) เท่ากับ c พอดี การพลิกหนึ่งครั้งคือเปลี่ยน bit ใด ๆ จาก 0 เป็น 1 หรือจาก 1 เป็น 0

แนวทาง — ต้องใช้อะไร & คิดยังไง

ข้อนี้ใช้การพิจารณาทีละ bit เพราะในนิยามของ OR แต่ละ bit position เป็นอิสระต่อกัน ผลของ bit หนึ่งไม่กระทบอีก bit เราจึงตัดสินใจแยกทีละตำแหน่งได้เลย

แทนที่จะลองพลิกทุกแบบ (ซึ่งมีความเป็นไปได้มหาศาล) เราดู bit ตรงตำแหน่งเดียวกันของ a, b, c พร้อมกันด้วย & 1 แล้ว shift ทุกตัวไปขวาทีละตำแหน่งด้วย >> 1 จนกว่าทั้งสามจะกลายเป็น 0

1. initialize flips = 0 แล้ว loop ไปเรื่อย ๆ ตราบใดที่ a หรือ b หรือ c ยังไม่เป็น 0
2. ดึง bit ขวาสุดของทั้งสาม: bit_a = a & 1, bit_b = b & 1, bit_c = c & 1
3. ถ้า bit_c เป็น 1: ต้องมี a หรือ b เป็น 1 สักตัว ถ้าทั้งคู่เป็น 0 ให้ flips += 1
4. ถ้า bit_c เป็น 0: ทั้ง a และ b ห้ามมี 1 เลย ให้ flips += bit_a + bit_b
5. shift ทั้งสามไปขวาหนึ่งตำแหน่ง (a >>= 1, b >>= 1, c >>= 1) แล้ว loop ต่อ สุดท้าย return flips

ไล่ทีละสเต็ป

จำลอง a = 2 (010), b = 6 (110), c = 5 (101) ไล่จาก bit ขวาสุด

def min_flips(a, b, c):
    flips = 0
    # วนทีละบิตจนกว่าทั้งสามตัวจะหมดบิต
    while a or b or c:
        bit_a = a & 1
        bit_b = b & 1
        bit_c = c & 1
        if bit_c == 1:
            # c ต้องการ 1 ตรงตำแหน่งนี้
            # ถ้า a หรือ b มี 1 อยู่แล้วก็พอ ไม่งั้นต้องพลิก 1 ครั้ง
            if bit_a == 0 and bit_b == 0:
                flips += 1
        else:
            # c ต้องการ 0 ตรงตำแหน่งนี้ ต้องพลิกทุกบิตที่เป็น 1 ให้เป็น 0
            flips += bit_a + bit_b
        # เลื่อนไปดูบิตถัดไป
        a >>= 1
        b >>= 1
        c >>= 1
    return flips

print(min_flips(2, 6, 5))  # 3
print(min_flips(4, 2, 6))  # 0
print(min_flips(1, 2, 3))  # 0

3
0
0