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).
Solutions
Solution
class Solution {public int minimumOneBitOperations(int n) { int ans = 0; for (; n > 0; n >>= 1) { ans ^= n; } return ans; }}Video 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.