# 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.

`$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; } }

## 0 Comments