# 1022. Smallest Integer Divisible by K

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.

1. `\$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/]
2. 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;
}
}```

This site uses Akismet to reduce spam. Learn how your comment data is processed.