Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.
Example 1:
Input: a = 2, b = 6, c = 5 Output: 3 Explanation: After flips a = 1 , b = 4 , c = 5 such that (aORb==c)
Example 2:
Input: a = 4, b = 2, c = 7 Output: 1
Example 3:
Input: a = 1, b = 2, c = 3 Output: 0
Constraints:
1 <= a <= 10^91 <= b <= 10^91 <= c <= 10^9
Solution: Bit operation
If the bit of c is 1, a / b at least has one 1. cost = 1 – ((a | b) & 1)
If the bit of c is 0, a / b must be 0, cost = (a & 1) + (b & 1)
Time complexity: O(32)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int minFlips(int a, int b, int c) { int count = 0; for (int i = 0; i < 32; ++i) { if (c & 1) count += 1 - ((a | b) & 1); else count += (a & 1) + (b & 1); a >>= 1; b >>= 1; c >>= 1; } return count; } }; |