1318. Minimum Flips to Make a OR b Equal to c

Leetcode link

题目简介

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */

题目给我们 3 个数字，要求计算我们需要翻转 a 与 b 两个数字的多少比特位才能使得 a | b === c

返回需要翻转最少的比特位数量

解题思路

这题我们直接模拟即可

具体步骤为：

1. 每次获取 a b c 三个数字的最低比特位 bitA bitB bitC
2. 判断 bitA | bitB === bitC
3. 如果为真，代表不需要翻转，直接跳过，比较次低位比特位

4. 如果为假，此时有两种可能：

   1. bitC 是 1：说明 bitA 与 bitB 都是 0，此时我们任意翻转一个即可
   2. bitC 是 0：说明 bitA 与 bitB 至少有一个 1，我们把 1 翻转位 0 即可

5. 每次计算完成我们需要把三个数字向右移一位，然后继续重复步骤 1

6. 最后返回翻转的次数即可

Javascript

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var minFlips = function (a, b, c) {
    let res = 0

    while (a > 0 || b > 0 || c > 0) {
        const bitA = a & 1
        const bitB = b & 1
        const bitC = c & 1

        if ((bitA | bitB) !== bitC) {
            if (bitC === 1) {
                res++
            } else {
                res += bitA + bitB
            }
        }
        a >>= 1
        b >>= 1
        c >>= 1
    }

    return res
};

复杂度分析

时间

计算的次数取决于三个数字中最大的数字，所以我们要先求 max(a, b, c)

其次我们遍历的是 a b c 的二进制长度，所以需要取一个 log

最后结果为：O(log(max(a, b, c)))

空间

O(1)