Skip to main content
Talentd

Minimum One Bit Operations to Make Integers Zero - Solution & Explanation

HardDynamic ProgrammingBit ManipulationMemoization18 min readAsked at: Oracle, ServiceNow, Expedia +2
Practice this problem

Problem Statement

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

  • Change the rightmost (0th) bit in the binary representation of n.
  • Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th 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 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.

Example 2:

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

 

Constraints:

  • 0 <= n <= 109

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.

This function computes the recursive solution. It checks the highest set bit and recurses by flipping the bit using XOR and adjusting the metric accordingly. The base case is when n is 0.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n), where n is the input size.
Space Complexity: O(log n), due to the recursion stack.

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.

The iterative loop continuously XORs res with current num and shifts num right, mimicking recursive pattern iteratively.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Recursive Approach

Time Complexity: O(log n), where n is the input size.
Space Complexity: O(log n), due to the recursion stack.

Iterative Approach Using Bit Manipulation

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

Gray Code Inverse Transform (Gray Code to Binary Code)ā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(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

Video Solution

Minimum One Bit Operations to Make Integers Zero | Detailed Explanation | Leetcode 1611 | MIK ā€¢ codestorywithMIK ā€¢ 15,461 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

Practice Minimum One Bit Operations to Make Integers Zero with our built-in code editor and test cases.

Practice on FleetCode
Previous

Apply Bitwise Operations to Make Strings Equal

Next

Minimum Number of Operations to Make Array Continuous