runtime 0 ms, beats 100% of cpp submissions
O(log(n)) solution with explanation

tags: number

Reverse Integer

📖 description

給定一個 32 bit 的數字 x (signed) ，將數字反轉輸出，如果超過表示上限就回傳 0 ，過程中不能使用 64 bit 的數字做儲存

ex. 
    123 -> 321
   -123 -> -321

🧠 solution

因題目設定的限制，這題變得沒有那麼直接，需要針對可能出現超過限制的數值進行控制，當超過上限就直接回傳 0 即可

ex. 
    2147483647 -> 7463847412  (不符合，超過最大數字)
   -2147483647 -> -7463847412 (不符合，超過最小數字)

由於方便，我們可以將輸入的數字先轉換為負數，可以少考慮一種狀況 (負數的表示上限為 -2147483648)

而要判斷有沒有超過上限，不能直接與 INT_MAX, INT_MIN 比較大小，所以可以換個思路去跟 INT_MIN / 10 比較大小，但會出現兩種情況表示超過上限

  • num > INT_MIN / 10
  • num == INT_MIN / 10 且下一個加進來的位數小於 -8 (負數的表示上限為 -2147483648)

⏳ time complexity

迴圈的次數取決於輸入數字的位數，所以時間複雜度為 O(log(n)) (此處的 log 以 10 為底)
總時間複雜度 O(log(n))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int reverse(int x) {
        bool isneg = true;
        int lon = x;
        int l=0,now;
        if(lon>0) {       // 將輸入轉換成負數
            lon *= -1;
            isneg=false;
        }
        while(lon!=0){
            now = lon % 10;
            if (l < INT_MIN/10 || (l == INT_MIN / 10 && now < -8)){ // 判斷是否超過上限
                return 0;
            }
            l = l * 10 + now;
            lon /= 10;
        }
        if(!isneg) return -l; // 如果原本進來的是正數
        else return l;        // 反之
    }
};