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 的角度想有啥可以用的。次方就是指數,指數相對的就是對數

4=\log_3 81\!

那只要找到對數的方法就簡單啦。用 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 轉成 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!! 

更新 

好友 @武可 提供了 stackoverflow 上 power of three 的數學公式,附上來給各位參考。

 

對敏捷開發有興趣的朋友,可以參考我的粉絲專頁:91敏捷開發之路

對 TDD 課程有興趣的朋友,課程內容、大綱與學員心得,可以參考 skilltree 的公開課程:自動測試與 TDD 實務開發

若需要聯絡我,可以透過粉絲專頁私訊或是側欄的關於我。