Given an integer `n`

, you must transform it into `0`

using the following operations any number of times:

- Change the rightmost (
`0`

) bit in the binary representation of^{th}`n`

. - Change the
`i`

bit in the binary representation of^{th}`n`

if the`(i-1)`

bit is set to^{th}`1`

and the`(i-2)`

through^{th}`0`

bits are set to^{th}`0`

.

Return *the minimum number of operations to transform *`n`

* into *`0`

*.*

**Example 1:**

Input:n = 0Output:0

**Example 2:**

Input:n = 3Output:2Explanation: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 3:**

Input:n = 6Output:4Explanation: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.

**Example 4:**

Input:n = 9Output:14

**Example 5:**

Input:n = 333Output:393

**Constraints:**

`0 <= n <= 10`

^{9}

**Solution 1: Graycode**

Time complexity: O(logn)

Space complexity: O(1)

Ans is the order of n in graycode.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int minimumOneBitOperations(int n) { int ans = 0; while (n) { ans ^= n; n >>= 1; } return ans; } }; |