Get started

Minimum One Bit Operations to Make Integers Zero — Hard Problem & Solution

Two operations transform a binary number: flip the rightmost bit (bit 0); flip bit i + 1 only if bit i is 1 and bits i - 1 … 0 are all 0.

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue