1342. 将数字变成 0 的操作次数

🟢   🔖  位运算 数学  🔗 力扣 LeetCode

题目

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.

Example 1:

Input: num = 14

Output: 6

Explanation: Step 1: 14 is even; divide by 2 and obtain 7. Step 2: 7 is odd; subtract 1 and obtain 6. Step 3: 6 is even; divide by 2 and obtain 3. Step 4: 3 is odd; subtract 1 and obtain 2. Step 5: 2 is even; divide by 2 and obtain 1. Step 6: 1 is odd; subtract 1 and obtain 0.

Example 2:

Input: num = 8

Output: 4

Explanation: Step 1: 8 is even; divide by 2 and obtain 4. Step 2: 4 is even; divide by 2 and obtain 2. Step 3: 2 is even; divide by 2 and obtain 1. Step 4: 1 is odd; subtract 1 and obtain 0.

Example 3:

Input: num = 123

Output: 12

Constraints:

• 0 <= num <= 10^6

题目大意

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

示例 1：

输入： num = 14

输出： 6

解释： 步骤 1) 14 是偶数，除以 2 得到 7 。 步骤 2：7 是奇数，减 1 得到 6 。 步骤 3：6 是偶数，除以 2 得到 3 。 步骤 4：3 是奇数，减 1 得到 2 。 步骤 5：2 是偶数，除以 2 得到 1 。 步骤 6：1 是奇数，减 1 得到 0 。

示例 2：

输入： num = 8

输出： 4

解释： 步骤 1：8 是偶数，除以 2 得到 4 。 步骤 2：4 是偶数，除以 2 得到 2 。 步骤 3：2 是偶数，除以 2 得到 1 。 步骤 4：1 是奇数，减 1 得到 0 。

示例 3：

输入： num = 123

输出： 12

提示：

• 0 <= num <= 10^6

解题思路

可以使用位运算中的右移（即 num >>= 1）来模拟操作过程：

1. 初始化 steps 为 0，用于记录步数。
2. 特殊情况：如果 num == 0，不需要操作，返回 0。
3. 循环进行操作，直到 num == 0。
   • 如果 num 为偶数：直接除以 2（等价于右移 1 位，即 num >>= 1），步数加 1。
   • 如果 num 为奇数：要先减 1 然后除以 2（等价于右移 1 位），步数加 2。
   • 其中偶数可以通过 (num & 1) == 0 判断；
4. 返回步数。

复杂度分析

• 时间复杂度：O(log num)，num 的值在每次操作中减半，最多需要进行 O(log num) 次操作。
• 空间复杂度：O(1)，仅使用常量空间存储变量。

代码

/**
 * @param {number} num
 * @return {number}
 */
var numberOfSteps = function (num) {
	if (num === 0) return 0; // 边界条件：输入为 0

	let steps = 0;
	while (num > 1) {
		// 偶数操作 1 次，奇数操作 2 次
		steps += (num & 1) === 0 ? 1 : 2;
		num >>= 1; // 除以 2
	}
	return steps + 1; // 最后一步操作将 1 变为 0
};

相关题目

题号	标题	题解	标签	难度	力扣
2139	得到目标值的最少行动次数		贪心 数学	🟠	🀄️ 🔗
2169	得到 0 的操作数	[✓]	数学 模拟	🟢	🀄️ 🔗