Minimum One Bit Operations to Make Integers Zero
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 ofn. - Change the
i^thbit in the binary representation ofnif the(i-1)^thbit is set to1and the(i-2)^ththrough0^thbits are set to0.
Return the minimum number of operations to transform n into 0.
Example 1
Input
n = 3Output
2The binary representation of 3 is "11"; it can be transformed as "11" -> "01" -> "00" in 2 operations.
Example 2
Input
n = 6Output
4The binary representation of 6 is "110"; it can be transformed as "110" -> "010" -> "011" -> "001" -> "000" in 4 operations.
Constraints
- 0 <= n <= 10^9