3790. Smallest All-Ones Multiple

MediumHash TableMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a positive integer k.

Your task is to find the smallest integer n that satisfies two conditions:

n is divisible by k.
n consists of only the digit 1 in its decimal representation (for example, 1, 11, 111, 1111, and so on).

Once you find this smallest n, you should not return n itself. Instead, return an integer representing the number of digits in the decimal representation of n.

If no such n exists, return -1.

Example walkthrough of the idea:

If k = 3, then 111 is divisible by 3 (since 111 / 3 = 37), and it is the smallest all-ones number that works. It has 3 digits, so the answer would be 3.
If k = 2, no number made up entirely of 1s can ever be divisible by 2, because all such numbers are odd. In this case, the answer would be -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Using modular arithmetic (remainder tracking) to find the smallest all-ones number divisible by k avoids building arbitrarily large integers.

Open in Flowchart

Intuition

The first thing to notice is when the answer can never exist. Every all-ones number (1, 11, 111, ...) ends in the digit 1, which means they are all odd. An odd number can never be divisible by an even number. So if k is even, we can immediately return -1. The same reasoning applies to numbers ending in 5 for divisibility by 5, but the key barrier we can detect up front is the even case.

Next, the natural approach is to simply build the all-ones numbers one digit at a time and check each one: is 1 divisible by k? Is 11? Is 111? And so on. The moment one of them is divisible by k, we report how many digits it has.

The problem with directly building these numbers is that they grow extremely fast. After just a few steps, the number becomes huge, making the divisibility check slow and the value impractical to store. To avoid this, we rely on a simple property of the modulo operation: to check divisibility, we only ever need to track the remainder when divided by k, not the full number.

Here is the clever part. Notice how each all-ones number is formed from the previous one:

11 = 1 * 10 + 1
111 = 11 * 10 + 1
1111 = 111 * 10 + 1

So if we know the remainder x of the current number when divided by k, the remainder of the next number is simply (x * 10 + 1) % k. This lets us move from one all-ones number to the next using only its remainder, keeping our values small and the computation fast. Whenever the remainder becomes 0, we have found a number divisible by k, and we return the current digit count.

Finally, why is it safe to stop after k iterations? Because there are only k possible remainder values (0 through k - 1). If we go through k steps without ever hitting a remainder of 0, the remainders must start repeating, which means we are stuck in a cycle and will never reach 0. At that point, we can safely conclude no valid n exists and return -1.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Simulation + Modulo Operation

We follow the simulation idea step by step, using only the remainder to keep our numbers small.

Step 1: Handle the impossible case.

First, we check if k is even. Since every all-ones number is odd, it can never be divisible by an even k. So if k % 2 == 0, we directly return -1.

Step 2: Initialize the starting state.

We set up two variables:

x = 1 % k — this is the remainder of the first all-ones number 1 when divided by k.
ans = 1 — this tracks the number of digits in the current all-ones number, starting at 1 for the number 1.

Step 3: Simulate building larger all-ones numbers.

We loop up to k times. In each iteration, we move from the current all-ones number to the next one (for example, from 11 to 111) by updating the remainder:

x = (x * 10 + 1) % k

This works because appending a 1 to a number is the same as multiplying it by 10 and adding 1. By taking the modulo at each step, the value of x always stays within the range 0 to k - 1, so we never deal with huge numbers.

After updating the remainder, we increase the digit count with ans += 1.

Step 4: Check for divisibility.

Right after each update, we check if x == 0. If it is, the current all-ones number is divisible by k, and we return ans as the number of digits.

Step 5: Decide when to give up.

We only loop k times because there are exactly k possible remainder values (0 through k - 1). If we never hit a remainder of 0 within these k steps, the remainders must begin to repeat, meaning we are caught in a cycle that can never reach 0. In that case, we exit the loop and return -1.

Complexity Analysis:

Time complexity: O(k), since we perform at most k iterations, each doing constant work.
Space complexity: O(1), since we only use a fixed number of variables (x and ans) regardless of the size of k.

Example Walkthrough

Let's trace through the solution approach with a small example: k = 7.

Step 1: Handle the impossible case.

We check if k is even. Since 7 % 2 == 1, k is odd, so we don't return -1 here. We proceed.

Step 2: Initialize the starting state.

x = 1 % 7 = 1 — the remainder of the first all-ones number 1 when divided by 7.
ans = 1 — the digit count, starting at 1 for the number 1.

Before looping, note that x = 1, which is not 0, so the number 1 is not divisible by 7.

Step 3 & 4: Simulate and check divisibility.

We loop up to k = 7 times, updating the remainder with x = (x * 10 + 1) % k and checking if x == 0.

Iteration	Calculation	New `x`	`ans`	All-ones number	`x == 0`?
1	`(1 * 10 + 1) % 7 = 11 % 7`	`4`	`2`	`11`	No
2	`(4 * 10 + 1) % 7 = 41 % 7`	`6`	`3`	`111`	No
3	`(6 * 10 + 1) % 7 = 61 % 7`	`5`	`4`	`1111`	No
4	`(5 * 10 + 1) % 7 = 51 % 7`	`2`	`5`	`11111`	No
5	`(2 * 10 + 1) % 7 = 21 % 7`	`0`	`6`	`111111`	Yes

At iteration 5, the remainder x becomes 0, meaning 111111 is divisible by 7. Indeed, 111111 / 7 = 15873.

Step 4: Return the answer.

Since x == 0 and the current digit count is ans = 6, we return 6.

Verifying the key insight:

Notice that throughout the entire process, the value of x always stayed within the range 0 to 6 (never exceeding k - 1 = 6). We never had to store or compute the large number 111111 directly — only its remainder. This is what keeps the computation fast and the values small.

A quick look at the give-up condition:

Had k been even — say k = 4 — Step 1 would have caught it immediately and returned -1, since no all-ones number (always odd) can be divisible by 4. For odd values where no all-ones number works, the loop would run all k iterations without ever reaching x == 0, and we would return -1 after the remainders began cycling.

Solution Implementation

1class Solution:
2    def minAllOneMultiple(self, k: int) -> int:
3        # A repunit (number made only of 1s) ends in digit 1, so it is always odd.
4        # Therefore it can never be divisible by an even k.
5        if k % 2 == 0:
6            return -1
7
8        # remainder tracks the value of the current repunit modulo k.
9        # We start with the repunit "1".
10        remainder = 1 % k
11        # length counts how many digits (1s) are in the current repunit.
12        length = 1
13
14        # We iterate at most k times: by the pigeonhole principle, if a repunit
15        # divisible by k exists, its length is at most k (only k possible remainders).
16        for _ in range(k):
17            # If the current repunit is divisible by k, return its length.
18            if remainder == 0:
19                return length
20            # Extend the repunit by appending another 1: R_{n+1} = R_n * 10 + 1.
21            # Keep only the remainder modulo k to avoid overflow concerns.
22            remainder = (remainder * 10 + 1) % k
23            length += 1
24
25        # No repunit up to length k is divisible by k.
26        return -1
27

1class Solution {
2    /**
3     * Finds the length of the smallest positive multiple of k that is
4     * composed entirely of the digit 1 (i.e., a "repunit": 1, 11, 111, ...).
5     *
6     * @param k the divisor
7     * @return the number of digits in the smallest qualifying multiple,
8     *         or -1 if no such multiple exists
9     */
10    public int minAllOneMultiple(int k) {
11        // If k is even, every all-ones number ends in 1 (odd),
12        // so it can never be divisible by k.
13        if ((k & 1) == 0) {
14            return -1;
15        }
16
17        // remainder of the current repunit modulo k.
18        // Start with the value "1" (mod k) before entering the loop body.
19        int remainder = 1 % k;
20
21        // length tracks the number of digits in the current repunit.
22        int length = 1;
23
24        // Iterate at most k times: by the pigeonhole principle, if the
25        // remainder has not reached 0 after k steps, it never will,
26        // since there are only k distinct possible remainders.
27        for (int i = 0; i < k; i++) {
28            // Build the next repunit's remainder:
29            // appending a digit '1' means newValue = oldValue * 10 + 1.
30            remainder = (remainder * 10 + 1) % k;
31            length++;
32
33            // A remainder of 0 means the repunit is divisible by k.
34            if (remainder == 0) {
35                return length;
36            }
37        }
38
39        // No qualifying multiple found within the search bound.
40        return -1;
41    }
42}
43

1class Solution {
2public:
3    int minAllOneMultiple(int k) {
4        // A repunit (number made only of 1s) is always odd.
5        // If k is even, it can never divide an odd number, so no answer exists.
6        if ((k & 1) == 0) {
7            return -1;
8        }
9
10        // remainder holds the current repunit modulo k.
11        // Start with the remainder of the 1-digit repunit (value 1).
12        int remainder = 1 % k;
13
14        // length tracks how many digits the current repunit has.
15        int length = 1;
16
17        // Iteratively build longer repunits: append a digit '1' each step.
18        // By pigeonhole, within k iterations the remainder must repeat or hit 0.
19        for (int i = 0; i < k; ++i) {
20            // Appending a '1' is equivalent to: newValue = oldValue * 10 + 1.
21            // Work modulo k to keep numbers small and avoid overflow.
22            remainder = (remainder * 10 + 1) % k;
23            ++length;
24
25            // A zero remainder means the current repunit is divisible by k.
26            if (remainder == 0) {
27                return length;
28            }
29        }
30
31        // No repunit divisible by k was found within the search bound.
32        return -1;
33    }
34};
35

1/**
2 * Finds the length of the smallest positive integer composed only of the
3 * digit '1' (e.g. 1, 11, 111, ...) that is divisible by `k`.
4 * Returns -1 if no such number exists.
5 *
6 * @param k - The divisor to test against.
7 * @returns The number of digits ('1's) in the smallest valid multiple, or -1.
8 */
9function minAllOneMultiple(k: number): number {
10    // A repunit (number made only of '1's) always ends in '1', so it is odd
11    // and never ends in 0 or 5. Therefore it can never be divisible by an
12    // even number. Short-circuit this impossible case immediately.
13    if ((k & 1) === 0) {
14        return -1;
15    }
16
17    // `remainder` tracks the current repunit value modulo `k`.
18    // Start with the single-digit repunit "1": 1 % k.
19    let remainder: number = 1 % k;
20
21    // `length` counts how many '1' digits the current repunit has.
22    let length: number = 1;
23
24    // The remainder is divisible by k when it becomes 0.
25    // By the pigeonhole principle, if no zero remainder appears within
26    // `k` iterations, the remainders must cycle and zero will never occur.
27    for (let i = 0; i < k; i++) {
28        // Append another '1' digit to the repunit, keeping only the remainder
29        // to prevent integer overflow: (...111 * 10 + 1) % k.
30        remainder = (remainder * 10 + 1) % k;
31        length++;
32
33        // A remainder of 0 means the current repunit is divisible by k.
34        if (remainder === 0) {
35            return length;
36        }
37    }
38
39    // No repunit divisible by k was found within the search bound.
40    return -1;
41}
42```
43
44**A note on correctness / alternative perspective:**
45
46The original code (and this faithful rewrite) only excludes even `k`, but a repunit also can't be divisible by any multiple of `5` (since it never ends in `0` or `5`). For inputs that are odd multiples of `5` (e.g. `k = 5`, `15`, `25`), the loop will simply run its full course and correctly return `-1` — just less efficiently. If you'd prefer to short-circuit that case too, you could replace the guard with:
47
48```typescript
49if (k % 2 === 0 || k % 5 === 0) {
50    return -1;
51}
52

Time and Space Complexity

Time Complexity: O(k). The function first checks whether k is even, which takes constant time. The core of the algorithm is a single for loop that iterates at most k times. Within each iteration, only constant-time operations are performed: a multiplication, an addition, a modulo operation x = (x * 10 + 1) % k, an increment, and a comparison. Since the loop runs O(k) times and each iteration costs O(1), the overall time complexity is O(k).
Space Complexity: O(1). The algorithm uses only a fixed number of variables (x and ans) to track the current remainder and the length of the repunit. The memory consumption does not grow with the input size k, so the space complexity is constant, O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Building the actual repunit number instead of tracking only the remainder

A very common mistake is to literally construct the all-ones number (1, 11, 111, ...) and then test divisibility with n % k == 0. While this seems like the most direct translation of the problem, it fails badly:

Integer overflow / performance collapse: In languages with fixed-width integers (C++, Java), the repunit overflows after about 18–19 digits, producing wrong answers. In Python, integers grow arbitrarily large, so there is no overflow, but each % k operation on a number with thousands of digits becomes expensive, degrading performance significantly.

Problematic code:

class Solution:
    def minAllOneMultiple(self, k: int) -> int:
        if k % 2 == 0:
            return -1
        n = 0
        for length in range(1, k + 1):
            n = n * 10 + 1   # n becomes a gigantic integer
            if n % k == 0:
                return length
        return -1

Solution: Always carry only the remainder forward using the identity R_{n+1} mod k = (R_n * 10 + 1) mod k. This keeps every value bounded between 0 and k - 1, guaranteeing constant-size arithmetic at each step.

remainder = (remainder * 10 + 1) % k

Pitfall 2: Looping the wrong number of times (off-by-one in the bound)

It is easy to misjudge how many iterations are needed before concluding -1. Some implementations loop only k - 1 times, or stop the loop one step too early, causing a valid answer of length k to be missed.

The key insight is the pigeonhole principle: there are exactly k distinct remainders (0 to k - 1). If a divisible repunit exists, its length is at most k. So you must allow the digit count to reach k. In the given solution, the loop checks remainder == 0 before extending, and the initial state already represents length 1, so across the k iterations all lengths from 1 to k are examined. Restructuring the loop carelessly can break this coverage.

Solution: Either check the remainder at the start of each of k iterations (as in the reference code), or explicitly iterate lengths from 1 through k inclusive. Verify with a boundary case where the answer equals k (for example, k = 3 yields length 3).

Pitfall 3: Forgetting the `1 % k` initialization edge case

When k = 1, the first repunit 1 is already divisible by k, and the answer should be 1. If you initialize remainder = 1 instead of remainder = 1 % k, then for k = 1 the remainder starts at 1 (not 0), and the first divisibility check fails incorrectly.

Problematic code:

remainder = 1   # wrong for k = 1

Solution: Initialize with remainder = 1 % k so that k = 1 correctly yields a remainder of 0 on the first check and returns 1.

remainder = 1 % k

Pitfall 4: Misreading the return value — returning `n` instead of the digit count

The problem explicitly asks for the number of digits, not the repunit itself. A natural slip is to return the constructed number or its string form. Always return length, the count of 1s, which directly matches the required output.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering