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

tags: number

Palindrome Number

📖 description

給定一個 32 bit 的數字 x (sighed)，判斷是否為回文數字

ex.
    121 -> 121  (回文)
   -121 -> 121- (非回文)

🧠 solution

check head and tail

這題可以跟回文字串一樣使用字串的形式來檢測，看頭跟尾的數字是否相等，但因為數字不像 string 可以確定頭尾，所以需要一些額外時間去找，這樣做的好處是可以提早找到不合的，或許能更早結束。

revert half

也可以換一種想法，只要把數字反轉並看看是否與原數字相等就可以了。

ex.
    121 -> 121 (相等)
    123 -> 321 (不相等)

此方法還可以進一步加速，只需要轉換一半，確認原數字的左半與右半是否相等。

⏳ time complexity

兩種方法的時間複雜度都與輸入數字的位數有關 O(log(n)) (此處的 log 以 10 為底)
總時間複雜度 O(log(n))

📝 code

check head and tail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;  // 如果數字小於 0 表示不可能構成回文
        int high = 1;
        while(x/high >= 10){   // 找到最高位
            high*=10;
        }
        while(x>0){
            if(x/high != x%10) return false; // 如果頭尾不相等提早結束
            x%=high;                         // 把最高位去除
            x/=10;                           // 把最低位去除
            high/=100;                       // 去頭去尾，最高位少了兩位
        }
        return true;
    }
};

revert half

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0 || (x%10==0 && x!=0)) return false;  // 如果數字小於 0 或是最低位是 0 表示不可能構成回文
        int re = 0;
        while(x > re){                              // 只做一半
            re = re * 10 + x%10;
            x /= 10;
        }
        return re == x || re/10 == x;               // 考慮到數字位數為奇數或偶數
    }
};