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

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