Minimum One Bit Operations to Make Integers Zero
HardPrompt
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 ofn. - Change the
ithbit in the binary representation ofnif the(i-1)thbit is set to1and the(i-2)ththrough0thbits are set to0.
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is based on establishing a recurrence relation that defines the solution for n in terms of a solution for a smaller number. By analyzing the structure of the operations, we can find a relationship between the operations needed for a number n and the operations for the number m that remains after removing n's most significant bit (MSB).
Algorithm
- Define a recursive function, let's call it
solve(n). - The base case for the recursion is
solve(0) = 0. - For any
n > 0, find the position of its most significant bit (MSB), let's sayk. This means2^k <= n < 2^(k+1). - The number
ncan be expressed asn = 2^k + m, wherem = n - 2^k. - The recurrence relation is
solve(n) = (2^(k+1) - 1) - solve(m). - The function computes this value and returns it. The initial call is
solve(n).
Walkthrough
Let f(n) be the minimum number of operations to convert n to 0. We can derive a recurrence relation by considering the MSB of n. Let the MSB be at position k, so n = 2^k + m where m < 2^k. To turn off the k-th bit, we must first transform the number into the form ...1100...0, specifically 2^k + 2^(k-1). This involves transforming m to 2^(k-1). After flipping the k-th bit, we are left with 2^(k-1), which we then need to transform to 0. A deep analysis of this process reveals a surprisingly simple recurrence relation: f(2^k + m) = (2^(k+1) - 1) - f(m). The base case is f(0) = 0. This relation can be implemented directly using a recursive function.
class Solution { public int minimumOneBitOperations(int n) { if (n == 0) { return 0; } // Find k, the position of the most significant bit. // For n > 0, k = floor(log2(n)). int k = 0; while ((1 << (k + 1)) <= n && (1 << (k + 1)) > 0) { k++; } // m is the remaining part of n after removing the MSB. int m = n - (1 << k); // The recurrence relation is f(n) = (2^(k+1) - 1) - f(m) // where n = 2^k + m. return ((1 << (k + 1)) - 1) - minimumOneBitOperations(m); }}Complexity
Time
O(log n). The number of recursive calls is at most the number of bits in `n`. Finding the MSB inside each call also takes logarithmic time relative to the value of `n` in that call.
Space
O(log n), due to the recursion stack depth, which is at most the number of bits in `n`.
Trade-offs
Pros
The code is a direct translation of the mathematical recurrence, making it relatively easy to understand if the recurrence is known.
It correctly solves the problem by breaking it down into smaller subproblems.
Cons
Incurs overhead from recursive function calls.
Uses stack space proportional to the number of bits in
n, which could be a concern for extremely large numbers (though not an issue with the given constraints).
This approach optimizes the recursive solution by converting it into an iterative process. By unrolling the recursion, we can eliminate the function call overhead and the need for stack space, thus improving space efficiency. The same underlying recurrence relation, f(2^k + m) = (2^{k+1} - 1) - f(m), is used, but it's applied iteratively.
Algorithm
- Initialize a result variable,
ans, to 0. - Loop as long as
nis greater than 0. - Inside the loop, find the position
kof the most significant bit (MSB) of the currentn. - Update the result using the formula:
ans = (2^(k+1) - 1) - ans. - Remove the MSB from
nto process the next part of the number:n = n - 2^k(orn = n XOR 2^k). - After the loop terminates,
ansholds the final result.
Walkthrough
The recursive structure can be transformed into a loop that processes the bits of n from most significant to least significant. We maintain a result variable that accumulates the answer according to the recurrence. In each iteration, we identify the MSB of the current value of n, apply the iterative formula derived from the recurrence, and then strip off that MSB to prepare for the next iteration. This continues until n becomes 0.
class Solution { public int minimumOneBitOperations(int n) { int ans = 0; while (n > 0) { // Find k, the position of the most significant bit. int k = 0; while ((1 << (k + 1)) <= n && (1 << (k + 1)) > 0) { k++; } // Apply the iterative version of the recurrence. // This formula is derived by unrolling the recursion. ans = ((1 << (k + 1)) - 1) - ans; // Remove the MSB from n for the next iteration. n -= (1 << k); } return ans; }}Complexity
Time
O(log n). The loop runs once for each set bit in `n`. In the worst case, it runs `log n` times. Finding the MSB in each step also contributes to the logarithmic complexity.
Space
O(1), as we only use a few variables to store the state.
Trade-offs
Pros
More space-efficient than the recursive approach as it uses constant extra space.
Avoids potential stack overflow errors for very large inputs.
Generally faster due to the absence of function call overhead.
Cons
The logic behind the iterative update
ans = (2^(k+1) - 1) - ansmight be less intuitive to derive compared to the recursive formulation.
This highly efficient approach is based on the insight that the problem is equivalent to converting a number from Gray code to its standard binary representation. The sequence of numbers generated by the allowed operations follows the binary-reflected Gray code sequence. The number of operations to transform n to 0 is simply the index of n in this sequence. This index can be found using a clever bitwise algorithm.
Algorithm
- Initialize a result variable,
result, with the value ofn. - Create a loop that continues as long as
nshifted to the right is greater than 0. - In each iteration, right-shift
nby one bit (n >>= 1). - XOR the
resultwith the new value ofn(result ^= n). - After the loop finishes,
resultwill hold the binary representation corresponding to the Gray coden, which is the minimum number of operations.
Walkthrough
The operations defined in the problem correspond to moving between adjacent values in a Gray code sequence. The k-th number in this sequence (starting from k=0) is G(k) = k XOR (k >> 1). The problem asks for the minimum operations to get from n to 0, which is the index k such that G(k) = n. We need to find k given n. This is the inverse operation of generating a Gray code.
The binary representation k can be recovered from its Gray code n using the following relations:
- The most significant bit of
kis the same as the MSB ofn. - For any other bit
i,k_i = n_i XOR k_{i+1}.
This can be computed efficiently with a loop: k = n XOR (n >> 1) XOR (n >> 2) XOR .... This series of XORs can be calculated with a simple loop.
class Solution { public int minimumOneBitOperations(int n) { int result = n; // The loop computes result = n ^ (n >> 1) ^ (n >> 2) ^ ... // In each step, n is right-shifted, and the result is updated. while ((n >>= 1) > 0) { result ^= n; } return result; }}Complexity
Time
O(log n), as the loop runs once for each bit in the number `n`.
Space
O(1), using only a single extra variable for the result.
Trade-offs
Pros
Extremely efficient in both time and space.
The implementation is very concise and elegant.
It is one of the fastest possible solutions due to its direct computation using simple bitwise operations.
Cons
The connection to Gray codes is not immediately obvious from the problem statement and requires a deeper insight into the problem's structure.
Solutions
Solution
class Solution {public int minimumOneBitOperations(int n) { int ans = 0; for (; n > 0; n >>= 1) { ans ^= n; } return ans; }}class Solution {public: int minimumOneBitOperations(int n) { int ans = 0; for (; n > 0; n >>= 1) { ans ^= n; } return ans; }};class Solution: def minimumOneBitOperations(self, n: int) -> int: ans = 0 while n: ans ^= n n >>= 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.