1611. Minimum One Bit Operations to Zero

The problem

Given an integer n, you must transform it into 0 using the following operations any number of times:

Change the rightmost (0^th) bit in the binary representation of n.
Change the i^th bit in the binary representation of n if the (i-1)^th bit is set to 1 and the (i-2)^th through 0^th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Example 1:

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2^nd operation since the 0^th bit is 1.
"01" -> "00" with the 1^st operation.

Example 2:

Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2^nd operation since the 1^st bit is 1 and 0^th through 0^th bits are 0.
"010" -> "011" with the 1^st operation.
"011" -> "001" with the 2^nd operation since the 0^th bit is 1.
"001" -> "000" with the 1^st operation.

Constraints:

0 <= n <= 10⁹

Approach overview

Problem Overview: Given an integer n, compute the minimum number of operations required to transform it to 0. The operation flips the least significant bit or flips the i-th bit only when the (i−1)-th bit is 1 and all lower bits are 0. The optimal solution relies on the relationship between these operations and Gray code transformations.

Approach 1: Recursive + Memoization (O(log n) time, O(log n) space)

This approach models the problem using recursion based on the highest set bit. Let k be the position of the most significant bit in n. To clear that bit, you must first transform the lower bits into a specific pattern, flip the bit, then revert the pattern. The recurrence becomes f(n) = (1 << (k + 1)) - 1 - f(n ^ (1 << k)). Memoization stores previously computed values to avoid recomputation. The recursion depth is proportional to the number of bits, giving O(log n) time.

This method fits naturally with dynamic programming and memoization. It mirrors how the operation sequence builds from smaller subproblems.

Approach 2: Iterative Bit Manipulation (Gray Code Insight) (O(log n) time, O(1) space)

The minimum operations correspond to converting a Gray code number back to its binary index. If you repeatedly XOR the current value with itself shifted right, you effectively compute the inverse Gray code. Start with ans = 0. While n > 0, perform ans ^= n and shift n >>= 1. Each iteration removes one bit from consideration.

This works because the operation rules mimic Gray code transitions where only one bit changes between states. The XOR accumulation reconstructs the total number of steps needed to reach zero. The algorithm processes each bit once, giving O(log n) time with constant memory using bit manipulation.

Recommended for interviews: The iterative bit-manipulation solution is what most interviewers expect. It demonstrates recognition of the Gray code pattern and produces a concise O(log n), O(1) solution. The recursive DP version is useful for explaining the underlying recurrence and showing how the pattern emerges.

Approach 1: Recursive Approach

The idea is to use a recursive function to determine the minimum number of operations needed to reduce the given number n to 0. Consider each bit change step as a recursive call, effectively exploring the tree of possibilities until we reach 0.

We need to account for the operation rules defined in the problem, particularly handling the change in the i-th bit when needed.

Python

def minimum_one_bit_operations(num):
    if num == 0:
        return 0
    x = 1
    bit = 0
    while (x << 1) <= num:
        x <<= 1
        bit += 1
    return minimum_one_bit_operations(num ^ x) + (1 << bit)

n = 6
print(minimum_one_bit_operations(n))

Java

public class Main {
    public static int minimumOneBitOperations(int num) {
        if (num == 0) return 0;
        int x = 1, bit = 0;
        while ((x << 1) <= num) {
            x <<= 1;
            bit++;
        }
        return minimumOneBitOperations(num ^ x) + (1 << bit);
    }

    public static void main(String[] args) {
        int n = 6;
        System.out.println(minimumOneBitOperations(n));
    }
}

C++

#include <iostream>
#include <cmath>
using namespace std;

int minimumOneBitOperations(int num) {
    if (num == 0) return 0;
    int x = 1, bit = 0;
    while ((x << 1) <= num) {
        x <<= 1;
        bit++;
    }
    return minimumOneBitOperations(num ^ x) + (1 << bit);
}

int main() {
    int n = 6;
    cout << minimumOneBitOperations(n) << endl;
    return 0;
}

JavaScript

function minimumOneBitOperations(num) {
    if (num === 0) return 0;
    let x = 1, bit = 0;
    while ((x << 1) <= num) {
        x <<= 1;
        bit++;
    }
    return minimumOneBitOperations(num ^ x) + (1 << bit);
}

let n = 6;
console.log(minimumOneBitOperations(n));

#include <stdio.h>

int minimumOneBitOperations(int num) {
    if (num == 0) return 0;
    int x = 1, bit = 0;
    while ((x << 1) <= num) {
        x <<= 1;
        bit++;
    }
    return minimumOneBitOperations(num ^ x) + (1 << bit);
}

int main() {
    int n = 6;
    printf("%d\n", minimumOneBitOperations(n));
    return 0;
}

using System;

public class Program {
    public static int MinimumOneBitOperations(int num) {
        if (num == 0) return 0;
        int x = 1, bit = 0;
        while ((x << 1) <= num) {
            x <<= 1;
            bit++;
        }
        return MinimumOneBitOperations(num ^ x) + (1 << bit);
    }

    public static void Main() {
        int n = 6;
        Console.WriteLine(MinimumOneBitOperations(n));
    }
}

The Python function uses recursion, identifying the bit to manipulate using shifts and XOR operations.

Complexity

Time Complexity: O(log n)
Space Complexity: O(log n)

Try this approach in the editor

Approach 2: Iterative Approach Using Bit Manipulation

This approach removes recursion and implements the bit operations iteratively. The key step involves simulating the recursive logic using a while loop and maintaining a transformation count.

Python

def minimum_one_bit_operations(num):
    res = 0
    while num > 0:
        res ^= num
        num >>= 1
    return res

n = 6
print(minimum_one_bit_operations(n))

Java

public class Main {
    public static int minimumOneBitOperations(int num) {
        int res = 0;
        while (num > 0) {
            res ^= num;
            num >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 6;
        System.out.println(minimumOneBitOperations(n));
    }
}

C++

#include <iostream>
using namespace std;

int minimumOneBitOperations(int num) {
    int res = 0;
    while (num > 0) {
        res ^= num;
        num >>= 1;
    }
    return res;
}

int main() {
    int n = 6;
    cout << minimumOneBitOperations(n) << endl;
    return 0;
}

JavaScript

function minimumOneBitOperations(num) {
    let res = 0;
    while (num > 0) {
        res ^= num;
        num >>= 1;
    }
    return res;
}

let n = 6;
console.log(minimumOneBitOperations(n));

#include <stdio.h>

int minimumOneBitOperations(int num) {
    int res = 0;
    while (num > 0) {
        res ^= num;
        num >>= 1;
    }
    return res;
}

int main() {
    int n = 6;
    printf("%d\n", minimumOneBitOperations(n));
    return 0;
}

using System;

public class Program {
    public static int MinimumOneBitOperations(int num) {
        int res = 0;
        while (num > 0) {
            res ^= num;
            num >>= 1;
        }
        return res;
    }

    public static void Main() {
        int n = 6;
        Console.WriteLine(MinimumOneBitOperations(n));
    }
}

The Python solution handles num's bits in a loop, handling transformations using XOR operations iteratively.

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Gray Code Inverse Transform (Gray Code to Binary Code)

This problem essentially asks for the inverse transformation of Gray code at position n, i.e., constructing the original number from the Gray code.

Let's first review how to convert binary code to binary Gray code. The rule is to keep the most significant bit of the binary code as the most significant bit of the Gray code, while the second most significant bit of the Gray code is obtained by XORing the most significant bit and the second most significant bit of the binary code. The remaining bits of the Gray code are computed similarly to the second most significant bit.

Suppose a binary number is represented as B_{n-1}B_{n-2}...B_2B_1B_0, and its Gray code representation is G_{n-1}G_{n-2}...G_2G_1G_0. The most significant bit is kept, so G_{n-1} = B_{n-1}; and for other bits G_i = B_{i+1} \oplus B_{i}, where i=0,1,2..,n-2.

So what is the inverse transformation from Gray code to binary code?

We can observe that the most significant bit of the Gray code is kept, so B_{n-1} = G_{n-1}; and B_{n-2} = G_{n-2} \oplus B_{n-1} = G_{n-2} \oplus G_{n-1}; and for other bits B_i = G_{i} \oplus G_{i+1} cdots \oplus G_{n-1}, where i=0,1,2..,n-2. Therefore, we can use the following function rev(x) to obtain its binary code:

int rev(int x) {
    int n = 0;
    for (; x != 0; x >>= 1) {
        n ^= x;
    }
    return n;
}

The time complexity is O(log n), where n is the integer given in the problem. The space complexity is O(1).

TypeScript

function minimumOneBitOperations(n: number): number {
    let ans = 0;
    for (; n > 0; n >>= 1) {
        ans ^= n;
    }
    return ans;
}

func minimumOneBitOperations(n int) (ans int) {
	for ; n > 0; n >>= 1 {
		ans ^= n
	}
	return
}

Rust

impl Solution {
    pub fn minimum_one_bit_operations(mut n: i32) -> i32 {
        let mut ans = 0;
        while n > 0 {
            ans ^= n;
            n >>= 1;
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Approach	Time Complexity: O(log n) Space Complexity: O(log n)
Iterative Approach Using Bit Manipulation	Time Complexity: O(log n) Space Complexity: O(1)
Gray Code Inverse Transform (Gray Code to Binary Code)	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive with Memoization	O(log n)	O(log n)	When explaining the recurrence or building intuition from subproblems
Iterative Bit Manipulation (Inverse Gray Code)	O(log n)	O(1)	Best practical and interview solution; minimal code and constant memory

Frequently asked questions

Is Minimum One Bit Operations to Make Integers Zero easy or hard?

The problem is rated Hard because the optimal solution depends on recognizing the Gray code relationship behind the allowed bit operations. Once the pattern is known, the implementation itself is short and runs in O(log n) time.

Minimum One Bit Operations to Make Integers Zero Python/Java solution

In Python or Java, the core logic is a short loop: initialize ans = 0, then repeatedly perform ans ^= n and shift n >>= 1 until n becomes 0. This computes the inverse Gray code and returns the minimum operations in O(log n) time.

How to solve Minimum One Bit Operations to Make Integers Zero in O(log n)?

Use the inverse Gray code trick. Initialize ans = 0 and repeatedly apply ans ^= n while shifting n right by one bit. Each iteration combines bit prefixes to reconstruct the minimum number of operations, finishing after processing all bits.

What is the best approach for Minimum One Bit Operations to Make Integers Zero?

The optimal approach uses a Gray code observation with bit manipulation. Repeatedly XOR the current value with itself shifted right (ans ^= n, n >>= 1). This effectively computes the inverse Gray code and returns the minimum number of operations in O(log n) time and O(1) space.

Is Minimum One Bit Operations to Make Integers Zero asked at Google/Amazon/Meta?

Bit manipulation and Gray code style problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests pattern recognition, recursion reasoning, and efficient bitwise transformations.

What data structure is used in Minimum One Bit Operations to Make Integers Zero?

No complex data structures are required. The optimal solution relies purely on bit manipulation operations like XOR and bit shifting. The recursive variant may use a hash map or array for memoization.

What is the time complexity of Minimum One Bit Operations to Make Integers Zero?

The optimal solution runs in O(log n) time because it processes each bit of the integer once. The iterative bit manipulation method shifts the number right in every step. Space complexity is O(1) since only a few variables are used.

Minimum One Bit Operations to Make Integers Zero solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach

Approach 2: Iterative Approach Using Bit Manipulation

Approach 3: Gray Code Inverse Transform (Gray Code to Binary Code)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum One Bit Operations to Make Integers Zero solution and explanation

The problem

Approach overview

Approach 1: Recursive Approach

Approach 2: Iterative Approach Using Bit Manipulation

Approach 3: Gray Code Inverse Transform (Gray Code to Binary Code)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems