Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1611 with 23 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1611 # by problem number
lcpy gen -s minimum_one_bit_operations_to_make_integers_zero # by problem name
n, you must transform it into 0 using the following operations any number of times:
n.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.n into 0.
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.
class Solution:
# Time: O(log n)
# Space: O(1)
def minimum_one_bit_operations(self, n: int) -> int:
# Valid states form a Gray code sequence ordered by operation count, so the
# distance from n to 0 is the Gray-to-binary decode of n.
result = 0
while n:
result ^= n
n >>= 1
return result
| Time | Space |
|---|---|
| O(log n) | O(1) |