LeetCode 1015(Daily)題解

內文包括許多Latex語句，使用閱讀器等工具閱讀可能造成閱讀障礙。

題目描述

給定一個正整數K，請回傳最小的正整數N的長度，使得N只包含數字1且能被K整除。如果不存在這樣的N，請回傳-1。

思考路徑

首先可以直接照題目來做

1. 如果最後一位是0, 2, 4, 5, 6, 8，直接回傳-1（因為不可能被整除）
2. n = 1並記錄長度length = 1
3. 循環
   1. 判斷n是否能被K整除，能的話回傳長度
   2. n = n * 10 + 1（在數字後面加一個1）
   3. 長度加一

但可以注意到

Note: n may not fit in a 64-bit signed integer.

所以要這麼做可以直接使用Python :)

Accepted
Runtime: 971ms Beats: 19.36%
Memory: 18.02MB Beats: 26.46%

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k%10 in [0, 2, 4, 5, 6, 8]:
        # if k%2 == 0 or k%5 == 0: # this also works
            return -1
        n = 1
        cnt = 1
        while True:
            if n%k == 0:
                return cnt
            n*=10
            n+=1
            cnt += 1

優化思路

可以發現這個解法非常的慢，大概是勉強通過（大概數字太大乘法很慢），所以可以使用數學優化，可以由

\[x_i = kc_i + d_i\]

其中$c_i$為商，$d_i$為餘數。則

\[x_i = 10x_{i-1}+1 = 10(kc_{i-1}+d_{i-1}) + 1 = 10kc_{i-1}+10d_{i-1}+1\]

使用餘式定理可以得到

\[d_i = x_i \mod k = 10d_{i-1}+1 \mod k\]

$d_i = 0$即為能被整除的條件，所以可以只記錄餘數來進行計算，這樣就不會有數字過大的問題。

程式碼實作

Python

Accepted
Runtime: 5ms Beats: 76.74%
Memory: 17.72MB Beats: 76.74%

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k%2 == 0 or k%5 == 0:
            return -1
        n = 1
        cnt = 1
        while True:
            n %= k
            if n == 0:
                return cnt
            n*=10
            n+=1
            cnt += 1
        

C++

Accepted
Runtime: 0ms Beats: 100%
Memory: 7.98MB Beats: 22.83%

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if(k%2==0 || k%5==0){
            return -1;
        }
        int n = 1;
        int l = 1;
        while(true){
            n %= k;
            if(n == 0){
                return l;
            }
            n = n*10+1;
            l += 1;
        }
    }
};