Number of Steps to Reduce a Number to Zero

Bit Manipulation

10 min

Problem Statement

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

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.

Solution (Bit Manipulation)

The operations can be mapped directly to bitwise checks. An even number has its least significant bit (LSB) as 0, and an odd number has its LSB as 1. Dividing by 2 is equivalent to a right bit shift.

Algorithm Steps

Initialize steps = 0.
While num is not 0:
Check if the number is even using (num & 1) == 0.
If it's even, right-shift the number: num >>= 1. This is a division by 2.
If it's odd, subtract 1: num -= 1.
Increment the steps counter in each case.
Return steps.

Number:

Current Number

(00001110)

Steps Taken

Initial number: 14

Number of Steps Solution


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