Given two positive integers start and goal, a bit flip changes one binary digit of start from 0 to 1 or from 1 to 0. Return the minimum number of bit flips needed to turn start into goal.
Example 1
Input: start = 10, goal = 7
Output: 3
Explanation: The aligned binary forms are 1010 and 0111. The bits at positions 0, 2, and 3, counted from the right starting at 0, differ. Flipping those three bits turns 1010 into 0111.
Example 2
Input: start = 1, goal = 1
Output: 0
Explanation: The two numbers already have the same binary representation, so zero flips are needed.
Approach
A flip affects exactly one position. Every position where start differs from goal needs at least one flip, and flipping each of those positions once is enough. The number of differing positions is therefore the minimum.
Bitwise XOR produces a 1 at each differing position and a 0 at each matching position. This creates a difference mask. Counting its set bits, the bits equal to 1, gives the answer. A scan of all 32 positions counts every set bit in the mask.
Algorithm
XOR the two inputs to get the difference mask.
Start the flip count at zero.
Read the rightmost bit of the mask with bitwise AND against
1and add the resulting0or1to the count.Shift the mask one position to the right to expose the next bit.
Repeat the read and shift for all 32 positions, then return the count. Equal inputs produce a zero mask, so the count stays at zero.
Dry Run
Minimum Bit Flips to Convert Number
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the minimum number of bit flips. int minBitsFlip(int start, int goal) { // XOR marks every position where the inputs differ. int differentBits = start ^ goal; int flips = 0; // Scan all 32 positions, including leading zeros. for (int bit = 0; bit < 32; bit++) { flips += (differentBits & 1); differentBits >>= 1; } return flips; }};// Driver codeint main() { int start = 10, goal = 7; // instance for class Solution Solution sol; int ans = sol.minBitsFlip(start, goal); cout << "The minimum bit flips to convert number is: " << ans; return 0;}Complexity Analysis
Time Complexity: O(1). The scan always checks exactly 32 positions.
Space Complexity: O(1). The method stores a mask and a fixed number of counters.
Interview follow-up Questions
Yes. Align the two numbers by their rightmost bit. Any leading position absent from the shorter number has value 0, so it contributes a flip exactly when the longer number has a 1 there.
Be the first to add a comment.