262. Fix the OR
A pair of control registers a and b drive a relay board, and the board only behaves correctly when the bitwise OR of the two registers equals the target mask c. A technician can flip any single bit (0 to 1 or 1 to 0) in either register, and each flip costs one unit of effort.
Return the minimum number of single-bit flips, summed over both registers, that makes (a OR b) == c. Positions where the target bit is 0 force both register bits to 0; positions where it is 1 need at least one register bit set. Aim for O(log max) time and O(1) extra space.
Example 1
- Input:
- a = 5, b = 9, c = 6
- Output:
- 4
- Explanation:
Bit 0 of the target is 0 and a, b both carry it (2 flips); bit 3 is 0 but only b has it (1 flip), and bit 1 needs one flip, giving 4.
Example 2
- Input:
- a = 8, b = 8, c = 8
- Output:
- 0
- Explanation:
8 OR 8 is already 8, so no flip is required.
Example 3
- Input:
- a = 1, b = 2, c = 12
- Output:
- 4
- Explanation:
Bits 2 and 3 of c are set but neither register has them (2 flips), and the stray bits 0 and 1 must be cleared (2 flips), total 4.
Constraints
1 ≤ a, b, c ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log max(a,b,c))
- Space
- O(1)