Minimum Flips to Make a OR b Equal to c
Medium · Bit Manipulation · Bit Manipulation
Problem
You are given three positive integers a, b and c. A flip changes one bit of a or of b from 0 to 1 or from 1 to 0.
Return the fewest flips that make a OR b equal to c, where OR is the bitwise or.
Each bit position can be fixed on its own: the bits of a and b at one position only affect the same position of the result.
Examples
Input: a = 2, b = 6, c = 5 Output: 3
In binary a = 010, b = 110, c = 101. Bit 0 needs a 1 (one flip), bit 1 is 1 in both but 0 in c (two flips): 3 in all.
Input: a = 4, b = 2, c = 7 Output: 1
4 OR 2 is 110; c is 111, so one flip sets bit 0.
Input: a = 1, b = 2, c = 3 Output: 0
1 OR 2 is already 3.
Constraints
- 1 <= a, b, c <= 10^9
Approaches
- Bit by bit — time O(log max), space O(1)
Follow-up
The same per-bit reasoning answers the question for AND and XOR, each with its own rule for a 0 and a 1 in c: see the use cases. With XOR the answer collapses to a single popcount.
Related problems
Start free on Cariara · Coding problems · System design studio
