Number of Steps to Reduce a Number to Zero

TL;DR

Count the steps to reduce a number to zero by dividing by 2 if even, subtracting 1 if odd. Simple simulation with O(log n) time complexity.

Understanding the Problem

Given an integer num, return the number of steps needed to reduce it to zero following these rules:

If the number is even: divide it by 2
If the number is odd: subtract 1

Why this matters: This problem teaches bit manipulation concepts and logarithmic time complexity. The pattern of halving (division by 2) appears frequently in:

Binary search algorithms
Tree traversal (binary trees have log n height)
Understanding how computers represent numbers in binary

Real-world example: Think of this like efficiently reducing a workload - you can either make small improvements (subtract 1) or make big leaps when conditions are right (divide by 2).

Solution Approach

The straightforward approach is to simulate the process exactly as described:

Start with a step counter at 0
While the number is greater than 0:
- Check if it’s even or odd
- Apply the appropriate operation
- Increment the step counter
Return the total steps

The key insight is that dividing by 2 (for even numbers) reduces the number much faster than subtracting 1 (for odd numbers).

Implementation

/**
 * @param {number} num
 * @return {number}
 */
const numberOfSteps = function (num) {
  let steps = 0;

  while (num > 0) {
    if (num % 2 === 0) {
      // Even number: divide by 2
      num /= 2;
    } else {
      // Odd number: subtract 1
      num--;
    }
    steps++;
  }

  return steps;
};

Why this works: We’re simply following the rules until we reach zero. Each iteration moves us closer to the goal.

Alternative: Bit Manipulation Approach

For those interested in optimization, there’s a clever bit manipulation solution:

const numberOfSteps = function (num) {
  if (num === 0) return 0;

  let steps = 0;

  while (num > 0) {
    // If last bit is 1 (odd), we'll subtract
    // If last bit is 0 (even), we'll divide
    steps += (num & 1) ? 1 : 0;  // Add 1 for odd numbers
    num >>= 1;                   // Right shift (divide by 2)
    if (num > 0) steps++;        // Count the division step
  }

  return steps;
};

This uses bitwise operations:

num & 1 checks if the last bit is 1 (odd number)
num >>= 1 shifts bits right (equivalent to dividing by 2)

Complexity Analysis

Time Complexity: O(log n) - Each division by 2 cuts the number in half, leading to logarithmic steps. Even with subtractions, the overall complexity remains O(log n).
Space Complexity: O(1) - Only using a few variables regardless of input size

Testing the Solution

Let’s walk through example inputs:

Example 1: num = 14

14 (even) → 7 (step 1: divide by 2)
7 (odd) → 6 (step 2: subtract 1)
6 (even) → 3 (step 3: divide by 2)
3 (odd) → 2 (step 4: subtract 1)
2 (even) → 1 (step 5: divide by 2)
1 (odd) → 0 (step 6: subtract 1)
Result: 6 steps

Example 2: num = 8

8 (even) → 4 (step 1)
4 (even) → 2 (step 2)
2 (even) → 1 (step 3)
1 (odd) → 0 (step 4)
Result: 4 steps

Edge cases:

num = 0: Returns 0 (already at zero)
num = 1: Returns 1 (one subtraction)
Powers of 2 (like 8, 16, 32): Mostly divisions, very fast

Key Takeaways

Simulation is often the simplest approach for straightforward problems
Dividing by 2 gives logarithmic time complexity
Modulo operator (%) is perfect for checking even/odd
The pattern of “halving” appears in many efficient algorithms
Sometimes the obvious solution is the best solution