Minimum Bit Flips to Convert Number

49
1

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 1 and add the resulting 0 or 1 to 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

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 code
int 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.

ArraysBit ManipulationTCS NQT

Read Similar Blogs

Comments0