Number of Steps to Reduce a Number to Zero

Easy
176.

Number of Steps to Reduce a Number to Zero

Number of Steps to Reduce a Number to Zero is an easy coding problem on math and bit manipulation, asked in Amazon, Adobe and Cognizant interviews.

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

In one step, if the current number is even you divide it by two; otherwise you subtract one from it.

Example 1

Input
num = 14
Output
6
Explanation
14 → 7 → 6 → 3 → 2 → 1 → 0.

Example 2

Input
num = 8
Output
4
Explanation
8 → 4 → 2 → 1 → 0.

Example 3

Input
num = 0
Output
0

Constraints

  • 0 <= num <= 1000000

Follow-up: In binary, each division is a right shift and each subtraction clears a set bit. Can you answer from the bit pattern alone?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} num
 * @return {number}
 */
var numberOfSteps = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Steps to Reduce a Number to Zero — Solution

Number of Steps to Reduce a Number to Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Steps to Reduce a Number to Zero is an easy coding problem on math and bit manipulation, asked in Amazon, Adobe and Cognizant interviews.

  • Difficulty: Easy
  • Topics: Math, Bit Manipulation
  • Asked at: Amazon, Adobe, Cognizant
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

In one step, if the current number is even you divide it by two; otherwise you subtract one from it.

Example 1

Input: num = 14
Output: 6
Explanation: 14 → 7 → 6 → 3 → 2 → 1 → 0.

Example 2

Input: num = 8
Output: 4
Explanation: 8 → 4 → 2 → 1 → 0.

Example 3

Input: num = 0
Output: 0

Constraints

  • 0 <= num <= 1000000

Follow-up: In binary, each division is a right shift and each subtraction clears a set bit. Can you answer from the bit pattern alone?

Hints for Number of Steps to Reduce a Number to Zero

  1. Hint 1

    Simulate the process directly; it terminates in O(log num) steps.

  2. Hint 2

    In binary, halving is a right shift and subtracting one from an odd number clears its lowest bit.

  3. Hint 3

    So the answer is (number of bits - 1) + (number of set bits), for num > 0.

How to solve Number of Steps to Reduce a Number to Zero

Simulate the process: halve when even, decrement when odd, and count steps. Each halving removes a bit, so the loop runs O(log num) times.

Approach

  1. While num > 0: if even, num //= 2; else num -= 1; increment the count.
  2. Return the count.

Why it works

In binary, subtracting one from an odd number clears the lowest bit and halving shifts right, so each set bit costs one decrement and each bit position (except the top) costs one shift. The simulation counts exactly those operations.

Complexity

  • Time — O(log num)
  • Space — O(1)

Pitfalls

  • The closed form is (bit length - 1) + popcount for num > 0; 0 needs zero steps.
  • Nothing here overflows — the value only ever decreases.

Reference solution

Python

def numberOfSteps(num: int) -> int:
    steps = 0
    while num > 0:
        num = num // 2 if num % 2 == 0 else num - 1
        steps += 1
    return steps

Java

public static int numberOfSteps(int num) {
    int steps = 0;
    while (num > 0) {
        num = num % 2 == 0 ? num / 2 : num - 1;
        steps++;
    }
    return steps;
}

C++

int numberOfSteps(int num) {
    int steps = 0;
    while (num > 0) {
        num = num % 2 == 0 ? num / 2 : num - 1;
        steps++;
    }
    return steps;
}

JavaScript

var numberOfSteps = function(num) {
    let steps = 0;
    while (num > 0) {
        num = num % 2 === 0 ? num / 2 : num - 1;
        steps++;
    }
    return steps;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation