Teaching Kids Programming – Min Number of Steps to Reduce a Number to Zero

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 <= 10^6

Simulation/Greedy Algorithm to Reduce Number to Zero

The division is always preferred as it will bring down the number more quickly than subtraction. However, the division is only applicable when number is even. We can then simulate the process by following this Greedy Strategy:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def numberOfSteps(self, num: int) -> int:
        ans = 0
        while num:
            if num & 1 == 0:
                num //= 2  # or n >>= 1
            else:
                num -= 1
            ans += 1
        return ans

class Solution:
    def numberOfSteps(self, num: int) -> int:
        ans = 0
        while num:
            if num & 1 == 0:
                num //= 2  # or n >>= 1
            else:
                num -= 1
            ans += 1
        return ans

The time complexity is O(LogN) and the space complexity is O(1)

Counting Ones and Zeros to Reduce Number to Zero

We can convert the number to binary and count how many zeros and ones in it. Each zero require one operation and each one requires two (subtract and divide by two). The leftmost zero is over-counted and we need to subtract one from the answer.

1
2
3
4
5
6

class Solution:
    def numberOfSteps(self, num: int) -> int:
        a = bin(num)[2:]
        ones = a.count('1')
        zeros = len(a) - ones
        return ones * 2 + zeros - 1

class Solution:
    def numberOfSteps(self, num: int) -> int:
        a = bin(num)[2:]
        ones = a.count('1')
        zeros = len(a) - ones
        return ones * 2 + zeros - 1

Converting the number to binary takes O(LogN) time and counting how many ones takes O(M) where M is the number of binary digits thus O(LogN).

See C++ implementation of reducing numbers to zeros: Iterative and Recursion Algorithms to Compute the Number of Steps to Reduce a Number to Zero

Reducing Numbers to Zeros or Reach Number to N

• Teaching Kids Programming – Minimum Moves to Reach Target Score with Constraints (Greedy Algorithm)
• Teaching Kids Programming – Min Number of Steps to Reduce a Number to Zero
• Iterative and Recursion Algorithms to Compute the Number of Steps to Reduce a Number to Zero

–EOF (The Ultimate Computing & Technology Blog) —