Number of Steps to Reduce a Number to Zero

Number of Steps to Reduce a Number to Zero - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: num = 14

› Output: 6

💡 Note: Step-by-step: 14 → 7 → 6 → 3 → 2 → 1 → 0. Total of 6 steps.

Example 2 — Small Number

$ Input: num = 8

› Output: 4

💡 Note: 8 → 4 → 2 → 1 → 0. All even numbers except the last step.

Example 3 — Edge Case

$ Input: num = 1

› Output: 1

💡 Note: Only one step needed: 1 → 0

Constraints

0 ≤ num ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Start with integer num = 14

Process

Apply rules: even ÷ 2, odd - 1

Output

Count total steps = 6

Key Takeaway

🎯 Key Insight: Each bit in the binary representation contributes to the step count

Asked in

L LeetCode 15 M Microsoft 8

The key insight is that we can either simulate the process step by step or use bit manipulation to calculate the result directly. The optimal approach uses the formula: count of 1-bits + total bits - 1. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation Approach	O(log n)	O(1)	Count 1-bits plus total bits minus 1 for optimal solution
Simulation Approach	O(log n)	O(1)	Follow the reduction rules step by step until num becomes 0

Bit Manipulation Approach — Algorithm Steps

Step 1: Count the number of 1-bits in binary representation
Step 2: Count total number of bits
Step 3: Return count of 1-bits + total bits - 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Form

Convert number to binary representation

Count Bits

Count 1-bits and total bits

Calculate

Formula: ones + total_bits - 1

Code -

solution.c — C

#include <stdio.h>

int countOnes(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int countBits(int n) {
    int count = 0;
    while (n) {
        count++;
        n >>= 1;
    }
    return count;
}

int solution(int num) {
    if (num == 0) return 0;
    
    int ones = countOnes(num);
    int totalBits = countBits(num);
    
    return ones + totalBits - 1;
}

int main() {
    int num;
    scanf("%d", &num);
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Bit counting operations are proportional to number of bits

⚡ Linearithmic

Space Complexity

O(1)

Only using variables for bit counting

✓ Linear Space

91.1K Views

Medium Frequency

~10 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler