Given a positive integer K, you need find 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.
Example 1:
Input:
1
Output:
1
Explanation:
The smallest answer is N = 1, which has length 1.
Example 2:
Input:
2
Output:
-1
Explanation:
There is no such positive integer N divisible by 2.
Example 3:
Input:
3
Output:
3
Explanation:
The smallest answer is N = 111, which has length 3.
Note:
1 <= K <= 10^5
Thoughts:
Two tricky parts.
$n = ($n * 10 +1) % $K;Suppose r = (aK + b) when r > K, next r supposed to be 10r+1 = 10aK + 10b + 1. Since 10aK is divisible by K, we just need to consider 10b + 1. b is r % K, so we can update r = r % K. [By https://leetcode.com/wangqiuc/]- The exit condition for loop, $n <= $K, actually, there always exist an answer, we can use while true instead.
Proof [By https://leetcode.com/starsthu2016/]
It is obvious that if K is the multiple of 2 or multiple of 5, N is definitely not multiple of K because the ones digit of N is 1. Thus, return -1 for this case.
If K is neither multiple of 2 nor multiple of 5, we have this theorem.
Theorem: there must be one number from the K-long candidates list [1, 11, 111, …, 111..111(with K ones)], which is the multiple of K.
Why? Let’s think in the opposite way. Is it possible that none of the K candidates is the multiple of K?
If true, then the module of these K candidate numbers (mod K) must be in [1, .., K-1] (K-1 possible module values). Thus, there must be 2 candidate numbers with the same module. Let’s denote these two numbers as N_i with i ones, and N_j with j ones and i<j.
Thus N_j-N_i = 1111…1000…0 with (j-i) ones and i zeros. N_j-N_i = 111..11 (j-i ones) * 100000..000 (i zeros). We know that N_i and N_j have the same module of K. Then N_j-N_i is the multiple of K. However, 100000..000 (i zeros) does not contain any factors of K (K is neither multiple of 2 nor multiple of 5). Thus, 111..11 (j-i ones) is the multiple of K. This is contradictory to our assumption that all K candidates including 111..11 (j-i ones) are not multiple of K.
Finally, we know that there is at least one number, from the first K candidates, which is the multiple of K.
class Solution {
/**
* @param Integer $K
* @return Integer
*/
function smallestRepunitDivByK($K) {
if($K % 2 == 0 || $K % 5 == 0){
return -1;
}
$n = 1;
$r = 1;
while($n <= $K ){
if($n % $K == 0){
return $r;
}
$n = ($n * 10 +1) % $K;
$r ++;
}
return -1;
}
}