LeetCode 326. Power of Three

LeetCode 326: Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

題目解釋：給一個整數 n，判斷是否為 3 的次方。
挑戰：不用迴圈或遞迴。

週日想透過 LeetCode 練一下手感，突然看到這一題，想說也太簡單了吧。3 的次方，有什麼難的？腦袋馬上有著滿滿的想法。

什麼，不可以用迴圈跟遞迴！？這該從哪切入才好？

---

沒啥想法？先寫一個測試案例出來就對了。

測試案例如下：

        [TestMethod]
        public void n_is_3_should_be_true()
        {
            var n = 3;
            Assert.IsTrue(new Solution().IsPowerOfThree(n));
        }

產品代碼思路

一開始看到 3 的次方，腦袋就是先想到「各數字相加，若能被 3 整除，就代表是 3 的倍數」。

喂！這跟 3 的次方沒有關係啊！

恩，沒有關係。那就改成：

1. n 除以 3, 若餘數不為 0，則 return false;
2. 若餘數為 0，則商數當下一次的 n，再次除以 3 運算。

就這麼簡單！但不用迴圈或遞迴該怎麼完成呢？

...
...
... ... ... 沒有，這算法就是得迴圈或遞迴

思路再繞個彎，既然是數學，從 Math 的角度想有啥可以用的。次方就是指數，指數相對的就是對數。

那只要找到對數的方法就簡單啦。用 Math.Log() 就可以了。但是 MSDN 的說明：Math.Log 方法 (Double, Double) 是回傳 double 的。

因此還需要判斷，這個 double 是否為整數。若為整數，代表 n 為 3 的次方數。

如何判斷一個 double 是否為整數

因為我實在不是很想用 ToString() 再去判斷有沒有小數點，所以我決定用 mod 1 取餘數是否為 0 判斷是否為整數。

產品代碼如下：

    public class Solution
    {
        public bool IsPowerOfThree(int n)
        {
            var o = Math.Log(n, 3);

            var p = o % 1;

            return p == 0;
        }
    }

通過測試。

Double 精準度問題

當測試案例 n 為 243 時，會發現期望為 3 的 5 次方，但 o 的值雖為 5，mod 1 後 p 的值卻為 0.999999，如下圖所示：

double 精準度問題

修正 double 精準度的問題，我決定用偷吃步，把 double 轉成 decimal 處理。產品代碼如下：

        public bool IsPowerOfThree(int n)
        {            
            var o = (decimal)Math.Log(n, 3);

            var r = o % 1;

            return r == 0;
        }

通過 n = 243 double 精準度測試失敗的問題。

當 n = 0 會 overflow exception

Math.Log() 當傳入 n 為 = 0 時，會拋 overflow exception，因為 n 只要是整數都可以傳入。所以直接針對 n 的範圍作限制與判斷。產品代碼如下：

    public class Solution
    {
        public bool IsPowerOfThree(int n)
        {
            if (n <= 0) return false;
            
            var o = (decimal)Math.Log(n, 3);

            var r = o % 1;

            return r == 0;
        }
    }

重構：inline variable

產品代碼如下：

    public class Solution
    {
        public bool IsPowerOfThree(int n)
        {
            if (n <= 0) return false;

            return (decimal)Math.Log(n, 3) % 1 == 0;
        }
    }

結論

難得有一題 LeetCode 兩行程式碼就搞定了，有趣。

透過 LeetCode 的練習，總能練習思路跟探索你平時可能不會用到的 API 。

練功就是這樣，你看練詠春的打木人樁，他不痛嗎？敵人可能站在那邊不動讓他打嗎？練到沒有槍頭也可以捅進去就對了！

心智開越多地圖，你未來能用的武器就越多，誰知道未來會碰到什麼樣的需求呢？腦袋跟寫 code 都是需要練習的，code for fun!!