Minimum Bit Flips to Convert Number

Easy
432.

Minimum Bit Flips to Convert Number

Minimum Bit Flips to Convert Number is an easy coding problem on bit manipulation, asked in Amazon and Adobe interviews.

A bit flip changes a single bit of a number's binary representation from 0 to 1 or from 1 to 0.

Given two non-negative integers start and goal, return the minimum number of bit flips that turn start into goal.

Example 1

Input
start = 10, goal = 7
Output
3

Example 2

Input
start = 3, goal = 4
Output
3

Example 3

Input
start = 8, goal = 8
Output
0

Constraints

  • 0 <= start, goal <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} start
 * @param {number} goal
 * @return {number}
 */
var minBitFlips = function(start, goal) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Bit Flips to Convert Number — Problem & Solution

Minimum Bit Flips to Convert Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Minimum Bit Flips to Convert Number is an easy coding problem on bit manipulation, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Bit Manipulation
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A bit flip changes a single bit of a number's binary representation from 0 to 1 or from 1 to 0.

Given two non-negative integers start and goal, return the minimum number of bit flips that turn start into goal.

Example 1

Input: start = 10, goal = 7
Output: 3

Example 2

Input: start = 3, goal = 4
Output: 3

Example 3

Input: start = 8, goal = 8
Output: 0

Constraints

  • 0 <= start, goal <= 1000000000

Hints for Minimum Bit Flips to Convert Number

  1. Hint 1

    Each differing bit needs exactly one flip, and identical bits need none.

  2. Hint 2

    start ^ goal marks precisely the differing positions.

  3. Hint 3

    So the answer is the popcount of that XOR.

How to solve Minimum Bit Flips to Convert Number

Each differing bit needs exactly one flip: popcount of start ^ goal.

Approach

  1. Return the number of set bits in start ^ goal.

Why it works

The XOR is 1 precisely at the positions that must change.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Identical to Hamming distance.

Reference solution

Python

def minBitFlips(start: int, goal: int) -> int:
    return bin(start ^ goal).count("1")

Java

public static int minBitFlips(int start, int goal) {
    int v = start ^ goal;
    int count = 0;
    while (v != 0) {
        v &= v - 1;
        count++;
    }
    return count;
}

C++

int minBitFlips(int start, int goal) {
    unsigned int v = (unsigned int) (start ^ goal);
    int count = 0;
    while (v) {
        v &= v - 1;
        count++;
    }
    return count;
}

JavaScript

var minBitFlips = function(start, goal) {
    let v = (start ^ goal) >>> 0;
    let count = 0;
    while (v > 0) {
        v &= v - 1;
        count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation