主題

LeetCode - 1015. Smallest Integer Divisible by K 解題心得

Not In My Back Yard | 2022-06-23 12:00:01 | 巴幣 0 | 人氣 42

題目連結:


題目意譯:
給定一個正整數 k,你需要找到最小正整數 n 之長度使得 n 可被 k 整除且 n 只包含數字 1。

回傳 n 的長度。如果不存在這樣子的 n 值,回傳 -1。

注: n 可能無法被容納進一個 64 位元有號整數內。

限制:
1 ≦ k ≦ 10 ^ 5



範例測資:
範例 1:
輸入: k = 1
輸出: 1
解釋: 最小的答案為 n = 1,其長度為 1。

範例 2:
輸入: k = 2
輸出: -1
解釋: 不存在正整數 n 可以被 2 整除。

範例 3:
輸入: k = 3
輸出: 3
解釋: 最小的答案為 n = 111,其長度為 3。


解題思維:
首先,我們可以看到只要 k 是 2 的倍數或是 5 的倍數就不可能存在題目所敘述的 n 值。因為我們能生成的數字是以 1 結尾的數字,而 2 的倍數至少需要是偶數結尾、5 的倍數則最少需要以 0 或是 5 結尾。

而我們可以看到當我們對以下數字:
1
11
111
1111
……
求餘數的時候等同於前一個數字的餘數乘以 10 再加 1。例如說已知 1111 除以 17 的餘數是 6,則 11111 除以 17 的餘數會是
6 × 10 + 1
除以 17 的餘數。也就是 10。

而餘數可能的值只有 0 ~ k - 1 這 k 個數值而已。因此如果我們做了上述的步驟 k + 1 次(也就是我們最後一項是在算 k + 1 個 1 除以 k 的餘數)的話,則根據鴿籠原理(Pigeonhole Principle)可知至少會有一個餘數值重複了一次。

因此如果我們上述的過程做了 k 次都沒有遇到餘數值為 0 的結果,則代表我們再繼續做下去也不可能遇到。因此此時就可以回傳 -1;反之,過程中有遇到的話就可以回傳這是第幾步,該步數即為所求。



但是實際上本題有更強烈的性質——即除了 2 或 5 的倍數以外的正整數皆存在這樣子的 n 值。而這個結論可以從數論中的歐拉定理(Euler's Theorem)推得:
已知
a ^ φ(k) ≡ 1 (模 k)
其中 a 、 k 為正整數(這邊的 k 可以對應到題目的 k),且 a 和 k 互質(即最大公因數(Greatest Common Divisor,GCD)等於 1),而 φ(k) 為歐拉總計函數(Euler's Totient Function),即 1(含)~ k(含)的正整數有多少與 k 互質。並且,上式當中的特殊等號「≡」代表「同餘」,也就是等號左右除以 k 之後的餘數(模 k)是相同的。

此時我們可以看到當 a 代入 10,並把等號右側的 1 丟到左側得到
10 ^ φ(k) - 1 ≡ 0 (模 k)
可以看到等號左邊是一個只由 9 組成的數字,且根據我們的 k 值之條件(不為 2 或 5 的倍數),等號會成立。因此,我們把等號左右兩邊同除以 9,得到
(10 ^ φ(k) - 1) ÷ 9 ≡ 0 (模 k)
此時等號左邊的數字便成為了只由 1 組成的數字。但是此時由於餘數除法只適用於模反元素(Modular Inverse,如這題)在的時候,也就是說此時上式只適用於 k 與 9 互質的時候。

因此我們少了所有 3 的倍數,需要額外證明才行。首先,假設我們現在有一數字 X,其為 3 的倍數。因此我們可以將 X 寫為 3 ^ d × m,其中 d ≧ 0 且 m 為一個不為 3 的倍數之正整數。

因此這邊的 m 可以根據上面歐拉定理推出自己的 n 值;而我們可以使用類似於這題的論述來證明所有 3 的某次方(即上式的 3 ^ d)也會有對應的 n 值。已知 m 與 3 ^ d 互質,因此我們可以藉由中國剩餘定理(Chinese Remainder Theorem)來得到整個 X 的 n 值。

以上,我們便證明了對於所有不是 2 或是 5 的倍數之正整數皆「存在」對應的 n 值。

結合我們一開始的結論——「最多做 k 次便可以判斷有沒有。」此時我們先排除掉 2 和 5 的倍數後,剩下可能的數字 k 必定會在 k 步以內找到餘數為 0 的 n 值。

因此不需額外判斷會不會碰到餘數 0(因為一定會有)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作