1342. Number of Steps to Reduce a Number to Zero

---

Description

Given an integer , return the number of steps to reduce it to zero.num

In one step, if the current number is even, you have to divide it by , otherwise, you have to subtract from it.21

 

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

---

Code

func numberOfSteps(num int) int {
	cnt := 0

	for num > 0 {
		if num%2 == 0 {
			num /= 2
		} else {
			num -= 1
		}

		cnt += 1
	}

	return cnt
}

 

함수는 주어진 숫자가 0이 될 때까지 반복문을 실행하고, 각 단계마다 조건에 따라 작업을 수행하고 단계 수를 증가시킵니다. 따라서 이 함수의 시간 복잡도는 입력값 num에 비례하여 O(log n)입니다. 이는 주어진 숫자를 반으로 나누는 작업을 반복할 때마다 주어진 숫자의 자릿수가 최소한 반으로 줄어들기 때문입니다. 따라서 입력값의 크기에 따라 반복 횟수가 로그 시간 복잡도로 감소합니다.