Minimum One Bit Operations to Make Integers Zero

HARD

Description

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⁹

Approaches

Checkout 3 different approaches to solve Minimum One Bit Operations to Make Integers Zero. Click on different approaches to view the approach and algorithm in detail.

Recursive Approach based on Recurrence Relation

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 say k. This means 2^k <= n < 2^(k+1).
The number n can be expressed as n = 2^k + m, where m = 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).

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 Analysis

Time Complexity: 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 Complexity: O(log n), due to the recursion stack depth, which is at most the number of bits in `n`.

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Minimum One Bit Operations to Make Integers Zero. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Minimum One Bit Operations to Make Integers Zero

Patterns:

Dynamic ProgrammingBit ManipulationMemoization

Companies:

Expedia |ServiceNow |McKinsey |