LeetCode 3790 - Smallest All-Ones Multiple

Difficulty: 🟡 Medium
Topics: Hash Table, Math

Solution

Problem Understanding

This problem asks us to find the smallest positive integer composed entirely of the digit 1 that is divisible by a given integer k. The input k is guaranteed to be between 2 and 100,000. We are asked not for the number itself, but for the number of digits in this number, which simplifies the task slightly because we do not need to store potentially very large numbers explicitly.

In other words, we are looking for the smallest integer n such that n % k == 0 and n consists only of digits 1 (like 1, 11, 111, etc.). If no such number exists (for example, when k is divisible by 2 or 5, as a number made entirely of ones cannot be divisible by 2 or 5), we return -1.

Key points to notice:

Numbers with only 1s grow very quickly, so constructing them naively could result in integer overflow.
We can leverage modular arithmetic: rather than constructing the full number, we can track the remainder when divided by k.
Edge cases include small numbers (k = 2, 5) where no solution exists and prime numbers where the solution might require many digits.

Approaches

Brute Force

The naive approach is to generate numbers consisting of only 1s incrementally: first 1, then 11, then 111, etc., and check each one for divisibility by k. This guarantees correctness because we are checking every candidate in increasing order.

However, this approach is infeasible for large k because the numbers grow exponentially in length and quickly exceed standard integer types. Constructing and storing such large numbers is both slow and memory-intensive.

Optimal Approach

The key observation is that we do not need the actual numbers; we only need their remainder modulo k. If num is a number consisting of d ones, its remainder modulo k can be updated iteratively:

remainder = (remainder * 10 + 1) % k

We start with remainder = 1 % k for the first digit and continue appending 1s until remainder == 0. To detect cases where no solution exists, we can keep track of all remainders seen. If a remainder repeats, we are in a loop and no solution exists.

This approach is efficient because the remainder can only take k distinct values (from 0 to k-1). Therefore, in the worst case, we perform at most k iterations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(10^d)	O(d)	Constructs large numbers explicitly, infeasible for large k
Optimal	O(k)	O(k)	Uses modular arithmetic and remainder tracking, efficient and safe

Algorithm Walkthrough

Initialize a set seen to keep track of remainders encountered.
Initialize remainder = 1 % k and length = 1 since the first number is 1.
Loop while remainder != 0:

a. If remainder has already been seen, return -1 because we are in a cycle and no solution exists.

b. Add the current remainder to seen.

c. Update the remainder using remainder = (remainder * 10 + 1) % k.

d. Increment length by 1. 4. When remainder == 0, return length.

Why it works:

The remainder of a number consisting only of 1s modulo k depends only on the previous remainder and the fact that we append a 1. By tracking remainders, we ensure we do not enter infinite loops. Since there are only k possible remainders, we either find a solution within k steps or detect that no solution exists.

Python Solution

class Solution:
    def minAllOneMultiple(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1
        
        seen = set()
        remainder = 1 % k
        length = 1
        
        while remainder != 0:
            if remainder in seen:
                return -1
            seen.add(remainder)
            remainder = (remainder * 10 + 1) % k
            length += 1
        
        return length

Implementation Walkthrough:

The initial check handles the edge cases where no solution is possible (k divisible by 2 or 5). We use a set to track remainders and avoid infinite loops. Each iteration simulates appending a 1 to the number without constructing it explicitly, using (remainder * 10 + 1) % k. The variable length tracks how many digits have been appended. When remainder == 0, we have found the smallest all-ones number divisible by k, so we return length.

Go Solution

func minAllOneMultiple(k int) int {
    if k % 2 == 0 || k % 5 == 0 {
        return -1
    }

    seen := make(map[int]bool)
    remainder := 1 % k
    length := 1

    for remainder != 0 {
        if seen[remainder] {
            return -1
        }
        seen[remainder] = true
        remainder = (remainder*10 + 1) % k
        length++
    }

    return length
}

Go-specific notes:

We use a map to track seen remainders because Go does not have a built-in set type. The algorithm logic mirrors Python, using remainder*10 + 1 modulo k. Overflow is not an issue because we only store remainders, which are at most k-1.

Worked Examples

Example 1: k = 3

Step	Remainder	Length	Seen
Start	1 % 3 = 1	1	{}
1	(1*10+1)%3 = 2	2	{1}
2	(2*10+1)%3 = 0	3	{1,2}

Output: 3

Example 2: k = 7

Step	Remainder	Length	Seen
Start	1 % 7 = 1	1	{}
1	(1*10+1)%7 = 4	2	{1}
2	(4*10+1)%7 = 6	3	{1,4}
3	(6*10+1)%7 = 5	4	{1,4,6}
4	(5*10+1)%7 = 2	5	{1,4,6,5}
5	(2*10+1)%7 = 0	6	{1,2,4,5,6}

Output: 6

Example 3: k = 2

Output: -1 because numbers consisting only of 1s cannot be divisible by 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k)	Each remainder is unique and we can see at most `k` remainders
Space	O(k)	The set of seen remainders can grow up to size `k`

This complexity is efficient because the number of iterations is bounded by k, and we do not need to construct large numbers explicitly.

Test Cases

# Provided examples
assert Solution().minAllOneMultiple(3) == 3  # 111 divisible by 3
assert Solution().minAllOneMultiple(7) == 6  # 111111 divisible by 7
assert Solution().minAllOneMultiple(2) == -1  # no solution
# Boundary cases
assert Solution().minAllOneMultiple(5) == -1  # divisible by 5, no solution
assert Solution().minAllOneMultiple(1) == 1   # edge case k=1, 1 itself
# Larger primes
assert Solution().minAllOneMultiple(13) == 6  # 111111 divisible by 13
assert Solution().minAllOneMultiple(17) == 16  # known sequence length
# Maximum k
assert Solution().minAllOneMultiple(100000) == -1  # divisible by 2 and 5, no solution

Test	Why
3	Checks basic divisibility and number of digits
7	Checks larger divisible number
2	No solution exists for even number
5	No solution exists for multiple of 5
1	Edge case for smallest k
13, 17	Tests with larger primes requiring multiple iterations
100000	Tests upper boundary of k

Edge Cases

Divisible by 2 or 5: Any k divisible by 2 or 5 cannot have an all-ones multiple