Welcome to Subscribe On Youtube

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)$.

  • 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;
    }
}


  • 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;
    }
};


  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions