#1611
Minimum One Bit Operations to Make Integers Zero
specialist · 960 · lc hard +32 · verified · 78.5% accepted · 1,207 likes · top 90%
Description
Given an integer n, reduce it to 0 using any sequence of these operations: (1) flip the rightmost bit; (2) flip bit i only when bit i-1 is 1 and all bits below i-1 are 0. Return the minimum total operations required.
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.
Code
1
2
3