Smallest Integer Divisible by K (M)
題目
Given a positive integer K, you need to find the length of the smallest positive integer N such that N is divisible by K, and N only contains the digit 1.
Return the length of N. If there is no such N, return -1.
Note: N may not fit in a 64-bit signed integer.
Example 1:
Input: K = 1
Output: 1
Explanation: The smallest answer is N = 1, which has length 1.
Example 2:
Input: K = 2
Output: -1
Explanation: There is no such positive integer N divisible by 2.
Example 3:
Input: K = 3
Output: 3
Explanation: The smallest answer is N = 111, which has length 3.
Constraints:
1 <= K <= 10^5
題意
找出一個最長的全部由1組成的整數N，使其能被K整除，
思路
由于N的長度不定，不能直接用普通遍歷去做，記由n個1組成的整數為\(f(n)\)，而\(f(n)\)除以K的余數為\(g(n)\)，則有\(g(n+1)=(g(n)*10+1)\%k\)，下證：
\[\begin{cases} f(n)\div K=a \\ g(n)=f(n)\ \%\ K \\ f(n+1)=f(n)\times10+1 \\ g(n+1)=f(n+1)\ \%\ K \end{cases} \ \Rightarrow\ \begin{cases} f(n)=a\times K\ +g(n) \\ g(n+1)=(f(n)\times10+1)\ \%\ K \end{cases} \ \Rightarrow\ g(n+1)=(10a \times K + 10 \times g(n)+1)\ \%\ K \equiv (10\times g(n)+1)\ \%\ K \]所以可以每次都用余數去處理，
另一個問題是確定回圈的次數，對于除數K，得到的余數最多有0~K-1這K種情況，因此當我們回圈K次都沒有找到整除時，其中一定有重復的余數，這意味著之后的回圈也不可能整除，所以最多回圈K-1次，
代碼實作
Java
class Solution {
public int smallestRepunitDivByK(int K) {
if (K % 5 == 0 || K % 2 == 0) {
return -1;
}
int len = 1, n = 1;
for (int i = 0; i < K; i++) {
if (n % K == 0) {
return len;
}
len++;
n = (n * 10 + 1) % K;
}
return -1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228728.html
標籤：其他
上一篇：線性表結構：陣列