Minimum Flips to Make a OR b Equal to c
題目描述
給定三個正整數 a, b, c。回傳翻轉 a 和 b 中位元的最少次數，使得 a OR b == c。翻轉一位算一次操作。
輸入：a = 2, b = 6, c = 5
輸出：3
解釋：翻轉後 a=1(001), b=4(100)，1 OR 4 = 5
輸入：a = 4, b = 2, c = 7
輸出：1
解題思路
逐位元檢查
用 a&1, b&1, c&1 取最低位，然後右移繼續檢查下一位，直到 a、b、c 都歸零
c 位元 = 1
需要 a|b = 1。若 a=0 且 b=0 → 翻轉 1 次（任選 a 或 b 翻一個）。否則已滿足，不翻
c 位元 = 0
需要 a=0 且 b=0。a 是 1 翻一次，b 是 1 翻一次，最多翻 2 次（用 bitA + bitB 計算）
累加翻轉數
所有位元的翻轉次數加總就是最終答案，例如 a=2(010), b=6(110), c=5(101) → 逐位分析得 flips=3
程式碼
C#
public class Solution {
public int MinFlips(int a, int b, int c) {
int flips = 0;
while (a > 0 || b > 0 || c > 0) {
int bitA = a & 1, bitB = b & 1, bitC = c & 1;
if (bitC == 1) {
// 需要 a|b = 1：至少一個是 1
if (bitA == 0 && bitB == 0) flips += 1;
} else {
// 需要 a=0 且 b=0：每個 1 都要翻
flips += bitA + bitB;
}
a >>= 1; b >>= 1; c >>= 1;
}
return flips;
}
}TypeScript
function minFlips(a: number, b: number, c: number): number {
let flips = 0;
while (a > 0 || b > 0 || c > 0) {
const bitA = a & 1, bitB = b & 1, bitC = c & 1;
if (bitC === 1) {
if (bitA === 0 && bitB === 0) flips += 1;
} else {
flips += bitA + bitB; // 每個 1 都要翻成 0
}
a >>= 1; b >>= 1; c >>= 1;
}
return flips;
}Python
def minFlips(a: int, b: int, c: int) -> int:
flips = 0
while a or b or c:
bit_a, bit_b, bit_c = a & 1, b & 1, c & 1
if bit_c == 1:
# 需要至少一個 1
if bit_a == 0 and bit_b == 0:
flips += 1
else:
# 兩個都必須是 0
flips += bit_a + bit_b
a >>= 1; b >>= 1; c >>= 1
return flips複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(max(log a, log b, log c)) | O(1) |
- Time：每次迴圈右移 1 位，最多執行 max(log2(a), log2(b), log2(c)) 次（即最大數的位元數），對於 32 位整數最多 30 次
- Space：只用了 flips 和三個 bit 變數，不隨輸入大小增長
邊界情況
- a、b、c 都是 0：不進入迴圈，flips = 0，已經滿足
0 OR 0 == 0 - c 等於 0：需要把 a 和 b 的所有 1 都翻成 0，flips = popcount(a) + popcount(b)
- a 和 b 已經滿足
a OR b == c：每一位都不需要翻轉，flips = 0 - a 等於 b：當 c 某位為 0 且 a 該位為 1 時，需要翻 2 次（a 和 b 都要翻）
圖解
圖表展示了逐位元的決策分支：根據 c 的位元值分成兩條路。 c=1 時只需確保至少一個 1（最多翻 1 次），c=0 時每個 1 都要翻掉（最多翻 2 次）。
進階觀點
💡面試追問
Q: 為什麼 c=0 時可能需要翻 2 次，但 c=1 時最多只翻 1 次？
A: OR 運算的特性決定了這個不對稱。c=1 只需「至少一個 1」，a 或 b 有一個是 1 就行，都是 0 才翻 1 次。但 c=0 要求 a OR b = 0，即 a 和 b 都必須是 0，所以每個 1 都要單獨翻轉，最多 2 次。
Q: 有沒有不用逐位元迴圈的位元運算解法？
A: 有。(a | b) ^ c 找出所有「需要改變」的位（OR 結果和 c 不同的位）。但這漏算了 c=0 且 a=b=1 的情況（需要翻 2 次但只計了 1 次）。用 a & b & ((a | b) ^ c) 找出這些額外翻轉位，最終答案 = popcount((a | b) ^ c) + popcount(a & b & ((a | b) ^ c))。
Q: 這種逐位元分析的思路還能用在哪些題？ A: 所有涉及 AND/OR/XOR 的位元操作題都可以逐位獨立分析，例如 LC 201 Bitwise AND of Numbers Range、LC 477 Total Hamming Distance。關鍵洞察是：位元運算的每一位互相獨立，可以分開處理再合併。
理解測驗
🤔 當 c 的某一位是 0，而 a 和 b 的對應位都是 1 時，需要翻轉幾次？
🤔 當 c 的某一位是 1，而 a=1, b=0 時，需要翻轉幾次？