Skip to content

3790. Smallest All-Ones Multiple

Description

You are given a positive integer k.

Find the smallest integer n divisible by k that consists of only the digit 1 in its decimal representation (e.g., 1, 11, 111, ...).

Return an integer denoting the number of digits in the decimal representation of n. If no such n exists, return -1.

 

Example 1:

Input: k = 3

Output: 3

Explanation:

n = 111 because 111 is divisible by 3, but 1 and 11 are not. The length of n = 111 is 3.

Example 2:

Input: k = 7

Output: 6

Explanation:

n = 111111. The length of n = 111111 is 6.

Example 3:

Input: k = 2

Output: -1

Explanation:

There does not exist a valid n that is a multiple of 2.

 

Constraints:

  • 2 <= k <= 105

Solutions

Solution 1: Simulation + Modulo Operation

First, if \(k\) is even, there is no valid \(n\) that satisfies the condition, so we directly return \(-1\).

Next, we can simulate the process of constructing an all-ones number \(n\) while taking the modulo with \(k\) to determine whether a valid \(n\) exists.

We loop \(k\) times to check whether there exists an all-ones number \(n\) divisible by \(k\) within these \(k\) iterations. In each iteration, we multiply the current remainder by \(10\), add \(1\), and then take the modulo with \(k\). If the remainder becomes \(0\) in some iteration, it means we have found a valid \(n\), and we return the current iteration count (i.e., the number of digits in the all-ones number). If no valid \(n\) is found after the loop ends, we return \(-1\).

The time complexity is \(O(k)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minAllOneMultiple(self, k: int) -> int:
        if k % 2 == 0:
            return -1
        x = 1 % k
        ans = 1
        for _ in range(k):
            x = (x * 10 + 1) % k
            ans += 1
            if x == 0:
                return ans
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minAllOneMultiple(int k) {
        if ((k & 1) == 0) {
            return -1;
        }

        int x = 1 % k;
        int ans = 1;

        for (int i = 0; i < k; i++) {
            x = (x * 10 + 1) % k;
            ans++;
            if (x == 0) {
                return ans;
            }
        }

        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minAllOneMultiple(int k) {
        if ((k & 1) == 0) {
            return -1;
        }

        int x = 1 % k;
        int ans = 1;

        for (int i = 0; i < k; ++i) {
            x = (x * 10 + 1) % k;
            ++ans;
            if (x == 0) {
                return ans;
            }
        }

        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minAllOneMultiple(k int) int {
    if k&1 == 0 {
        return -1
    }

    x := 1 % k
    ans := 1

    for i := 0; i < k; i++ {
        x = (x*10 + 1) % k
        ans++
        if x == 0 {
            return ans
        }
    }

    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function minAllOneMultiple(k: number): number {
    if ((k & 1) === 0) {
        return -1;
    }

    let x = 1 % k;
    let ans = 1;

    for (let i = 0; i < k; i++) {
        x = (x * 10 + 1) % k;
        ans++;
        if (x === 0) {
            return ans;
        }
    }

    return -1;
}

Comments