What is the main strategy for solving Minimum Flips to Make a OR b Equal to c?

The strategy involves evaluating each corresponding bit of a, b, and c, flipping bits only when necessary to satisfy the OR condition, and counting the minimal flips required.

Can I use string conversion to solve this problem?

While converting numbers to binary strings works, it is less efficient; bit masking and shifting are preferred for performance and clarity.

How do I handle a bit where both a and b have 1 but c has 0?

You must flip both bits from 1 to 0 in that position, as leaving either would prevent (a OR b) from matching c.

Is the number of flips always bounded?

Yes, the flips are bounded by the number of bits in the largest integer, since each bit can require at most two flips.

Does this problem pattern apply to AND or XOR operations?

Yes, similar bit-by-bit evaluation applies, but the flip conditions differ according to the AND or XOR logic.

#1318

Medium

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

或运算的最小翻转次数

给你三个正整数 a 、 b 和 c 。你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。示例 1：输入： a = 2, b = 6, c…

位运算

题目描述

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。

「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

示例 1：

输入：a = 2, b = 6, c = 5
输出：3
解释：翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c

示例 2：

输入：a = 4, b = 2, c = 7
输出：1

示例 3：

输入：a = 1, b = 2, c = 3
输出：0

提示：

1 <= a <= 10^9
1 <= b <= 10^9
1 <= c <= 10^9

lightbulb

解题思路

方法一：位运算

我们可以枚举 $a$ , $b$ , $c$ 的二进制表示的每一位，分别记为 $x$ , $y$ , $z$ 。如果 $x$ 和 $y$ 的按位或运算结果与 $z$ 不同，此时我们判断 $x$ 和 $y$ 是否都是 $1$ ，如果是，则需要翻转两次，否则只需要翻转一次。我们将所有需要翻转的次数累加即可。

时间复杂度 $O(\log M)$ ，其中 $M$ 是题目中数字的最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        ans = 0
        for i in range(32):
            x, y, z = a >> i & 1, b >> i & 1, c >> i & 1
            ans += x + y if z == 0 else int(x == 0 and y == 0)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(1) since the number of bits in the integers is bounded by 32 for standard integers, though for very large numbers it scales with the number of bits. Space complexity is O(1) because no extra data structures proportional to input size are required.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check bit-by-bit evaluation to see if flips are necessary.
question_mark
Expect handling both zero-to-one and one-to-zero flips in a single bit position.
question_mark
Optimize using bitwise masks instead of string conversion for efficiency.

warning

常见陷阱

外企场景

error
Forgetting to flip both a and b when c's bit is 0 but both a and b have 1.
error
Counting unnecessary flips when only one of a or b needs a change.
error
Iterating over a fixed number of bits without considering all significant bits of c.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimum flips to make a AND b equal to c, changing the bitwise operator from OR to AND.
arrow_right_alt
Minimum flips to make a XOR b equal to c, focusing on XOR-specific bit conditions.
arrow_right_alt
Minimum flips required when input numbers are constrained to smaller ranges or bit lengths.

help

常见问题

外企场景

继续练习

#1310 子数组异或查询 #1342 将数字变成 0 的操作次数 #1349 参加考试的最大学生数