Number of Steps to Reduce a Number to Zero

easy math bit manipulation

Problem

Given a non-negative integer num, in one step you can divide it by 2 if it is even, or subtract 1 if it is odd. Return the number of steps to reduce num to 0.

Inputnum = 14

Output6

14 → 7 → 6 → 3 → 2 → 1 → 0 = 6 steps.

num

def number_of_steps(num):
    steps = 0
    while num > 0:
        if num & 1: num -= 1
        else: num >>= 1
        steps += 1
    return steps

function numberOfSteps(num) {
  let steps = 0;
  while (num > 0) {
    if (num & 1) num -= 1;
    else num >>= 1;
    steps++;
  }
  return steps;
}

class Solution {
    public int numberOfSteps(int num) {
        int steps = 0;
        while (num > 0) {
            if ((num & 1) == 1) num -= 1;
            else num >>= 1;
            steps++;
        }
        return steps;
    }
}

int numberOfSteps(int num) {
    int steps = 0;
    while (num > 0) {
        if (num & 1) num -= 1;
        else num >>= 1;
        steps++;
    }
    return steps;
}

Explanation

We just follow the rules literally: keep going until num hits 0, counting every move. The neat part is checking even/odd with bit operations instead of division.

Each loop iteration looks at the lowest bit. num & 1 is 1 when the number is odd, so we subtract 1. Otherwise the number is even, and num >>= 1 shifts the bits right by one, which is the same as dividing by 2. Either way we add 1 to steps.

Why is this efficient? Halving an even number removes a bit, and subtracting 1 from an odd number clears its lowest bit. So the total step count is essentially the number of bits plus the number of 1-bits, which is small even for large numbers.

Example: num = 14 (binary 1110). The path is 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0: even/odd alternates as halve, minus-one, halve, minus-one, halve, minus-one, giving 6 steps.

Because each step removes a bit or clears one, the loop runs about log n times using constant space.

Time: O(log n) Space: O(1)