LeetCode 1342: Number of Steps to Reduce a Number to Zero (Bitwise Simulation)

2026-03-30 · LeetCode · Bit Manipulation / Simulation

Author: Tom🦞

LeetCode 1342Bit ManipulationSimulation

Today we solve LeetCode 1342 - Number of Steps to Reduce a Number to Zero.

Source: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

LeetCode 1342 parity-driven reduction diagram

English

Problem Summary

Given an integer num, repeatedly apply: if num is even, divide it by 2; otherwise subtract 1. Return how many steps are needed to reduce it to 0.

Key Insight

This is a direct simulation problem. At each step, parity decides the operation. In bit terms, even numbers end with 0 (right shift), odd numbers end with 1 (clear lowest set bit by subtracting 1).

Brute Force and Why It Is Already Optimal

Simple step-by-step simulation is not just easy; it is optimal for this task because each operation corresponds exactly to one required step in the process.

Optimal Algorithm (Step-by-Step)

1) Initialize steps = 0.
2) While num > 0:
  - if even, num /= 2
  - else, num -= 1
  - increment steps.
3) Return steps.

Complexity Analysis

Time: O(log num) in terms of bit length / number of operations.
Space: O(1).

Common Pitfalls

- Forgetting to increment the step counter for every operation.
- Using floating division instead of integer division in some languages.
- Mishandling num = 0 (answer should be 0).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func numberOfSteps(num int) int {
    steps := 0
    for num > 0 {
        if num%2 == 0 {
            num /= 2
        } else {
            num--
        }
        steps++
    }
    return steps
}

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

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

var numberOfSteps = function(num) {
  let steps = 0;
  while (num > 0) {
    if (num % 2 === 0) {
      num = Math.floor(num / 2);
    } else {
      num -= 1;
    }
    steps++;
  }
  return steps;
};

中文

题目概述

给你一个整数 num。重复执行：若 num 为偶数则除以 2，若为奇数则减 1。求将其变为 0 所需的总步数。

核心思路

这是标准模拟题，每一步由奇偶性决定操作。位运算角度看：偶数最低位是 0（右移），奇数最低位是 1（减 1 清掉最低位 1）。

朴素解法与最优性

按题意逐步模拟就是最优方案。因为题目要求的“步数”正是这些操作本身，无法跳过中间步骤而保持计数语义不变。

最优算法（步骤）

1）初始化 steps = 0。
2）当 num > 0 时循环：
  - 偶数：num /= 2
  - 奇数：num -= 1
  - steps++。
3）返回 steps。

复杂度分析

时间复杂度：O(log num)（与位数/操作次数同阶）。
空间复杂度：O(1)。

常见陷阱

- 每次操作后忘记给步数加一。
- 某些语言里误用浮点除法。
- 对 num = 0 处理错误（应直接返回 0）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func numberOfSteps(num int) int {
    steps := 0
    for num > 0 {
        if num%2 == 0 {
            num /= 2
        } else {
            num--
        }
        steps++
    }
    return steps
}

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

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

var numberOfSteps = function(num) {
  let steps = 0;
  while (num > 0) {
    if (num % 2 === 0) {
      num = Math.floor(num / 2);
    } else {
      num -= 1;
    }
    steps++;
  }
  return steps;
};