1342. Number of Steps to Reduce a Number to Zero (Easy)

Question

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7

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

1
2

Input: num = 123
Output: 12

Constraints

• 0 <= num <= 10^6

分析/解題

給定一個數字num，回傳其化簡至0所用的步驟數。
化簡的方法為：
若num此刻為偶數，將其除以2；若num此刻為奇數，將其減去1。

這題如果按照題目的條件一步一步走的話，
以二進位制來看，
我們會發現當尾端的bit是1時，就必須減去1並除以2 ，
也就是向右位移一個bit(這整件事情耗費了2步 )；
若bit是0時，則只需要除以2即可。

所以一個很簡單且直觀的寫法，就是利用迴圈，
當num還大於0時，檢查尾數的bit(可以用num & 1取得尾數是0或1)，
你可以用三元運算子 ，或者直接**(num & 1) + 1** 亦可，
請注意由於**&運算子的優先序較低** ，務必將num和1用括號包起來！
一路做到最後一個1，最後num等於0時就完成了。
(因為最後一個1不用再位移了，所以我們加總起來的步數最後要減去1)

這裡提供另一個想法：
當我們沒有限制計算bitCount的函式及轉換二進位/字串時，
可以推想到：

1. 所有1都必須被消成0 (每個bit ‘1’會耗費1步)
2. 要除以幾次2，端看最高位的1離個位數有多遠
   (轉成二進位的總長減去1等於總共要除以2的次數)

所以我們得到： 答案 = num的bit ‘1’數量 + num的長度 - 1

依此，寫成程式碼如下：

Java

Java的部分，我們可以利用bitCount和toBinaryString來達到要求。
(一步一步算的也有列出參考解，讀者可以自己試看看)

Python

Python的部分，由於bin()轉二進位時，前面會多出**’0b’** ，
所以計算長度時會多出2，後面的減1就會變成需要改成減3 ，
請再留意。其他跟Java大同小異。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(logN)/O(1)，但因為num最高就是10^6而已，如果你要宣稱num是constant，因此時間複雜度當成O(1)，個人覺得也是合理的。)

相似及延伸

Special Thanks suggestions/corrections from viewers:

From Cheng Rui Xie :
位元運算有很多有趣的 function 可以呼叫：
回傳以二為底的次方項：__lg(num)
回傳數字二進位後1的個數：__builtin_popcount(num)
只要取兩個的和即可且運算的時間＝O(1) 
(這個想法的O(1)也是將num當限定大小看待。)

(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**