Minimum One Bit Operations to Make Integers Zero

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

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.

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 \leq n \leq 10^9$

Submit your solution at here

Solution

Observation

My solution is based on this observation:

• Let’s say we have number $1xxxx$, in order to clear the highest $1$, there is no other way but to make it $11000$ first, and then clear the highest $1$ to form $1000$. This is not proven but I can’t find any other way to do it. So I just assume it. If you have a proof or a counter example on this I would gladly accept.
• From number $10000$, the only way to make it $00000$ is by transform it to $11000$, clear the highest $1$ and then recursively do it all over again. Let $n$ is the decimal form of the number we need to clear, the number of steps needed is $n \times 2-1$, or you can use bit operator with $i$ is the position of the $1$ bit, $(1<<(i+1)) - 1$

Complexity

• Time complexity: $O(log(n))$
• Space complexity: $O(log(n))$

Code

class Solution {
public:
    int costToClear(int bit) {
        return (1<<(bit+1)) - 1;
    }
    int minimumOneBitOperations(int n) {
        vector<int> f(31);// f[i] = cost to make xxxx to be 0000
        vector<int> g(31);// g[i] = cost to make xxxx to be 1000
        f[0] = (n&1)?1:0;
        g[0] = (n&1)?0:1;
        for(int i = 1;i<31;i++) {
            bool isSet = (n&(1<<i)) != 0;
            if(isSet) {
                g[i] = f[i-1];
                f[i] = g[i-1];// cost to make 1xxxx -> 11000
				f[i] += 1;// cost to make 11000 -> 1000
                f[i] += costToClear(i-1);// cost to make 1000 to become 0000
            } else {
                f[i] = f[i-1];
                g[i] = g[i-1];// cost to make 0xxxx -> 01000
				g[i] += 1;// cost to make 01000 -> 11000
                g[i] += costToClear(i-1);// cost to make 1000 to become 0000
            }
        }
        return f[30];
    }
};