Skip to content

1015. Smallest Integer Divisible by K

Description

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 <= 105

Solutions

Solution 1: Mathematics

Thinking

Building \(1,11,111,\ldots\) until divisibility overflows integers, and \(k\le 10^5\) forbids an unbounded search. Divisibility depends only on the remainder modulo \(k\).

\((10n+1)\bmod k\) is determined by \(n\bmod k\). There are only \(k\) remainders; if \(0\) never appears within \(k\) steps, later values cycle and no such number exists.

Starting from \(1\bmod k\) we iterate at most \(k\) times. The first zero remainder gives the number of digits; otherwise the answer is \(-1\).

We observe that the positive integer \(n\) starts with an initial value of \(1\), and each time it is multiplied by \(10\) and then \(1\) is added, i.e., \(n = n \times 10 + 1\). Since \((n \times 10 + 1) \bmod k = ((n \bmod k) \times 10 + 1) \bmod k\), we can determine whether \(n\) is divisible by \(k\) by calculating \(n \bmod k\).

We start from \(n = 1\) and calculate \(n \bmod k\) each time until \(n \bmod k = 0\). At this point, \(n\) is the smallest positive integer we are looking for, and its length is the number of digits in \(n\). Otherwise, we update \(n = (n \times 10 + 1) \bmod k\). If after looping \(k\) times we still haven't found \(n \bmod k = 0\), it means no such \(n\) exists, and we return \(-1\).

The time complexity is \(O(k)\) and the space complexity is \(O(1)\), where \(k\) is the given positive integer.

1
2
3
4
5
6
7
8
class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        n = 1 % k
        for i in range(1, k + 1):
            if n == 0:
                return i
            n = (n * 10 + 1) % k
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int smallestRepunitDivByK(int k) {
        int n = 1 % k;
        for (int i = 1; i <= k; ++i) {
            if (n == 0) {
                return i;
            }
            n = (n * 10 + 1) % k;
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int n = 1 % k;
        for (int i = 1; i <= k; ++i) {
            if (n == 0) {
                return i;
            }
            n = (n * 10 + 1) % k;
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func smallestRepunitDivByK(k int) int {
    n := 1 % k
    for i := 1; i <= k; i++ {
        if n == 0 {
            return i
        }
        n = (n*10 + 1) % k
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function smallestRepunitDivByK(k: number): number {
    let n = 1 % k;
    for (let i = 1; i <= k; ++i) {
        if (n === 0) {
            return i;
        }
        n = (n * 10 + 1) % k;
    }
    return -1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
impl Solution {
    pub fn smallest_repunit_div_by_k(k: i32) -> i32 {
        let mut n = 1 % k;
        for i in 1..=k {
            if n == 0 {
                return i;
            }
            n = (n * 10 + 1) % k;
        }
        -1
    }
}

Comments