[LEETCODE] 1342. Number of Steps to Reduce a Number to Zero

 

 

 

1342. Number of Steps to Reduce a Number to Zero

Given an integer num, return the number of steps to reduce it to zero.
In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

 

Example 1:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:

Input: num = 8
Output: 4
Explanation: 
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:

Input: num = 123
Output: 12

 

Constraints:

• 0 <= num <= 106

 

내 풀이

class Solution:
    def numberOfSteps(self, num: int) -> int:
        count = 0
        if num == 0:
            return num
        calc = num
        while True:
            count = count + 1
            if (calc%2 == 0):
                calc = calc/2
            else:
                calc = calc - 1
            if calc == 0:
                break 
        return count

 

다른 사람 풀이

# Count each 0 as 1.
# Count each 1 as 2 except the first 1.
# Time: O(bits of num)
# Space: O(bits of num)
# However num is bounded in 0 <= num <= 10^6, so time and space are both O(1) in this problem.

class Solution:
    def numberOfSteps (self, num: int) -> int:
        digits = f'{num:b}'
        return digits.count('1') - 1 + len(digits)
        
# O(1)space:

class Solution:
    def numberOfSteps (self, num: int) -> int:
        steps = num == 0
        while num > 0:
            steps += 1 + (num & 1)
            num >>= 1
        return steps - 1

 

무슨 비트를 이용해서 푸는거 같은데 신기...아 알았다 이진법을 이용해서 풀은 거였음 짝수는 무조건 2의 배수이므로