Minimum Bit Flips to Convert Number - Practice Coding Problems

Minimum Bit Flips to Convert Number - Problem

Bit Manipulation Easy

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.

For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.

Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

Input & Output

Example 1 — Basic Case

$ Input: start = 10, goal = 7

› Output: 3

💡 Note: 10 in binary is 1010, 7 in binary is 0111. We need to flip bits at positions 0, 1, and 3, so 3 flips total.

Example 2 — Same Numbers

$ Input: start = 3, goal = 4

› Output: 3

💡 Note: 3 in binary is 011, 4 in binary is 100. All three bit positions differ, so 3 flips needed.

Example 3 — Identical Numbers

$ Input: start = 5, goal = 5

› Output: 0

💡 Note: Both numbers are identical, so no bit flips are needed.

Constraints

0 ≤ start, goal ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Numbers

Two integers to compare bit by bit

Find Differences

Use XOR to identify differing bit positions

Count Flips

Number of differing positions equals minimum flips needed

Key Takeaway

🎯 Key Insight: XOR operation reveals exactly which bit positions differ between two numbers

Asked in

M Meta 15 G Google 12 M Microsoft 8 a Amazon 6

The key insight is that XOR reveals exactly which bit positions differ between two numbers. The optimal approach uses Brian Kernighan's algorithm to efficiently count set bits in the XOR result. Time: O(k) where k is number of different bits, Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Bit-by-Bit Comparison	O(log n)	O(1)	Compare each bit position individually and count differences
Brian Kernighan's Algorithm	O(k)	O(1)	Use Brian Kernighan's trick to count set bits efficiently
XOR and Bit Counting	O(log n)	O(1)	Use XOR to find different bits, then count set bits

Bit-by-Bit Comparison — Algorithm Steps

Step 1: Compare least significant bits
Step 2: Shift both numbers right by 1
Step 3: Repeat until both numbers become 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare LSB

Check if rightmost bits differ

Shift Right

Move to next bit position

Count Differences

Accumulate total flips needed

Code -

solution.c — C

#include <stdio.h>

int solution(int start, int goal) {
    int count = 0;
    while (start > 0 || goal > 0) {
        if ((start & 1) != (goal & 1)) {
            count++;
        }
        start >>= 1;
        goal >>= 1;
    }
    return count;
}

int main() {
    int start, goal;
    scanf("%d", &start);
    scanf("%d", &goal);
    int result = solution(start, goal);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

We check each bit position, maximum 32 positions for 32-bit integers

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables for counting and comparison

✓ Linear Space

78.1K Views

Medium Frequency

~10 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit-by-Bit Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler