Minimum One Bit Operations to Make Integers Zero

Hard
744.

Minimum One Bit Operations to Make Integers Zero

Minimum One Bit Operations to Make Integers Zero is a hard coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and Apple interviews.

Two operations transform a binary number:

  1. flip the rightmost bit (bit 0);
  2. flip bit i + 1 only if bit i is 1 and bits i - 1 … 0 are all 0.

Return the minimum number of operations that turns n into 0.

Example 1

Input
n = 3
Output
2
Explanation
11 → 01 → 00.

Example 2

Input
n = 6
Output
4
Explanation
110 → 010 → 011 → 001 → 000.

Example 3

Input
n = 0
Output
0

Constraints

  • 0 <= n <= 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} n
 * @return {number}
 */
var minimumOneBitOperations = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum One Bit Operations to Make Integers Zero — Solution

Minimum One Bit Operations to Make Integers Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum One Bit Operations to Make Integers Zero is a hard coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and Apple interviews.

Problem statement

Two operations transform a binary number:

  1. flip the rightmost bit (bit 0);
  2. flip bit i + 1 only if bit i is 1 and bits i - 1 … 0 are all 0.

Return the minimum number of operations that turns n into 0.

Example 1

Input: n = 3
Output: 2
Explanation: 11 → 01 → 00.

Example 2

Input: n = 6
Output: 4
Explanation: 110 → 010 → 011 → 001 → 000.

Example 3

Input: n = 0
Output: 0

Constraints

  • 0 <= n <= 1000000000

Hints for Minimum One Bit Operations to Make Integers Zero

  1. Hint 1

    The reachable states form a Gray-code ordering — each operation moves to an adjacent code word.

  2. Hint 2

    So the answer is the position of n in the standard reflected Gray code.

  3. Hint 3

    Converting a Gray code back to its index is the running XOR of the value's successive right shifts.

How to solve Minimum One Bit Operations to Make Integers Zero

The two operations are exactly the moves of the standard reflected binary (Gray) code: from a value you may step to the code word before or after it. So the minimum number of operations to reach 0 is the index of n in that code, and the Gray-to-binary conversion computes it directly.

Approach

  1. Start with ans = 0.
  2. While n > 0, XOR n into ans and shift n right by one.
  3. Return ans.

Why it works

The Gray code of an index i is i ^ (i >> 1), and the inverse is i = g ^ (g >> 1) ^ (g >> 2) ^ … — precisely the running XOR of shifts. Since the operations move one step along the code, the distance from n to the code word 0 is its index.

Complexity

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

Pitfalls

  • A breadth-first search over states is exponential and cannot reach 10^9.
  • The recursive formula f(n) = 2^k - f(n - 2^(k-1))… is equivalent but far easier to get wrong than the XOR-of-shifts form.
  • Use an unsigned or arithmetic shift, not a sign-propagating one; n is non-negative so either works here.

Reference solution

Python

def minimumOneBitOperations(n: int) -> int:
    ans = 0
    while n > 0:
        ans ^= n
        n >>= 1
    return ans

Java

public static int minimumOneBitOperations(int n) {
    int ans = 0;
    while (n > 0) {
        ans ^= n;
        n >>>= 1;
    }
    return ans;
}

C++

int minimumOneBitOperations(int n) {
    int ans = 0;
    unsigned int v = (unsigned int) n;
    while (v > 0) {
        ans ^= (int) v;
        v >>= 1;
    }
    return ans;
}

JavaScript

var minimumOneBitOperations = function(n) {
    var ans = 0, v = n;
    while (v > 0) {
        ans ^= v;
        v = Math.floor(v / 2);
    }
    return ans;
};

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

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Bit Manipulation