Problem#
Given an integer n
, you must transform it into 0
using the following operations any number of times:
Change the rightmost (0th
) bit in the binary representation of n
.
Change the ith
bit in the binary representation of n
if the (i-1)th
bit is set to 1
and the (i-2)th
through 0th
bits are set to 0
.
Return the minimum number of operations to transform n
into 0
.
Examples#
Example 1#
1
2
3
4
5
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#
1
2
3
4
5
6
7
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#
Solution#
Method 1 – Recursive Bit Manipulation (Gray Code)#
Intuition#
The problem is related to the minimum number of operations to convert n to 0 using Gray code properties. The operation count for each bit is recursive: flip the highest set bit, then recursively solve for the rest.
Approach#
If n == 0, return 0.
Find the highest set bit position k in n.
The answer is (1 « (k+1)) - 1 - minimumOneBitOperations(n ^ (1 « k)).
Recursively solve for n ^ (1 « k).
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
class Solution {
public :
int minimumOneBitOperations(int n) {
if (n == 0 ) return 0 ;
int k = 31 - __builtin_clz(n);
return (1 << (k+ 1 )) - 1 - minimumOneBitOperations(n ^ (1 << k));
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
func minimumOneBitOperations (n int ) int {
if n == 0 {
return 0
}
k := 0
for i := 31 ; i >= 0 ; i -- {
if n & (1 << i ) > 0 {
k = i
break
}
}
return (1 << (k + 1 )) - 1 - minimumOneBitOperations (n ^(1 << k ))
}
1
2
3
4
5
6
7
class Solution {
public int minimumOneBitOperations (int n) {
if (n == 0) return 0;
int k = 31 - Integer.numberOfLeadingZeros (n);
return (1 << (k+ 1)) - 1 - minimumOneBitOperations(n ^ (1 << k));
}
}
1
2
3
4
5
6
7
class Solution {
fun minimumOneBitOperations (n: Int): Int {
if (n == 0 ) return 0
val k = 31 - Integer .numberOfLeadingZeros(n)
return (1 shl (k+1 )) - 1 - minimumOneBitOperations(n xor (1 shl k))
}
}
1
2
3
4
5
6
class Solution :
def minimumOneBitOperations (self, n: int) -> int:
if n == 0 :
return 0
k = n. bit_length() - 1
return (1 << (k+ 1 )) - 1 - self. minimumOneBitOperations(n ^ (1 << k))
1
2
3
4
5
6
7
8
9
impl Solution {
pub fn minimum_one_bit_operations (n: i32 ) -> i32 {
if n == 0 {
return 0 ;
}
let k = 31 - n.leading_zeros();
(1 << (k+ 1 )) - 1 - Solution::minimum_one_bit_operations(n ^ (1 << k))
}
}
1
2
3
4
5
6
7
8
class Solution {
minimumOneBitOperations (n : number ): number {
if (n === 0 ) return 0 ;
let k = 31 ;
while (k >= 0 && ((n >> k ) & 1 ) === 0 ) k -- ;
return (1 << (k + 1 )) - 1 - this .minimumOneBitOperations (n ^ (1 << k ));
}
}
Complexity#
⏰ Time complexity: O(log n)
— Each recursion reduces the highest bit.
🧺 Space complexity: O(log n)
— For recursion stack.