Minimum Flips to Make a OR b Equal to c
The key idea
Work one bit at a time and treat the bits of
a, b, c independently. When c's bit is 0, every set bit in a and b at that position must be cleared, so add both. When c's bit is 1, you only need at least one set bit, so a flip is required only when a and b are both 0 there.Problem
Given 3 positive integers a, b and c, return the minimum number of flips required so that ( a OR b == c ), where OR is the bitwise-OR operation.
A flip changes a single bit of a or b from 1 to 0 or from 0 to 1.
Constraints
- 1 <= a <= 10^9
- 1 <= b <= 10^9
- 1 <= c <= 10^9
Examples
Input: a = 2, b = 6, c = 5
Output: 3
Input: a = 4, b = 2, c = 7
Output: 1
Input: a = 1, b = 2, c = 3
Output: 0
Complexity
Time: O(1) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Bit Manipulation problems
- Bitwise AND of Numbers RangeMEDIUM
- Minimum Array EndMEDIUM
- Missing NumberEASY
- Number of 1 BitsEASY
- Reverse BitsEASY
- Single NumberEASY
- Single Number IIMEDIUM
- Sum of All Subset XOR TotalsEASY
- Sum of Two IntegersMEDIUM