Minimum Flips to Make a OR b Equal to c ใน C++

สมมติว่าเรามีจำนวนบวก 3 ตัว a, b และ c เราต้องหาจำนวน bit flips น้อยที่สุดในบางบิตของ a และ b เพื่อให้ (a OR b == c) โดยพิจารณา bitwise OR operation

Flip operation คือการเปลี่ยนบิตเดี่ยว 1 เป็น 0 หรือ 0 เป็น 1 ใน binary representation ตัวอย่าง a = 0010, b = 0110, c = 0101 หลัง flips: a = 0001, b = 0100

ขั้นตอนการแก้ปัญหา

1. ans := 0
2. วนลูป i จาก 0 ถึง 31:
   • bitC := (c >> i) & 1
   • bitA := (a >> i) & 1
   • bitB := (b >> i) & 1
   • ถ้า (bitA OR bitB) ไม่เท่ากับ bitC:
     • ถ้า bitC เป็น 0:
       • ถ้า bitA = 1 และ bitB = 1 เพิ่ม ans 2, มิฉะนั้นเพิ่ม ans 1
     • มิฉะนั้น (bitC = 1) เพิ่ม ans 1
3. คืนค่า ans

ตัวอย่างโค้ด (C++)

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

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for(int i = 0; i < 32; i++) {
            int bitC = (c >> i) & 1;
            int bitA = (a >> i) & 1;
            int bitB = (b >> i) & 1;
            
            if((bitA | bitB) != bitC) {
                if(!bitC) {
                    if(bitA == 1 && bitB == 1) {
                        ans += 2;
                    } else {
                        ans += 1;
                    }
                } else {
                    ans += 1;
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.minFlips(2, 6, 5);
    return 0;
}

อินพุต

2 6 5

เอาต์พุต

3

คำอธิบายตัวอย่าง

a = 2 (0010), b = 6 (0110), c = 5 (0101)

• Bit 0: a=0, b=0, c=1 → (0|0)!=1 → flip 1 bit (ans=1)
• Bit 1: a=1, b=1, c=0 → (1|1)!=0 → both 1 → flip 2 bits (ans=3)
• Bit 2: a=0, b=1, c=1 → (0|1)==1 → OK
• Bit 3: a=0, b=0, c=0 → OK

รวม 3 flips