Problem Description

You need to find the smallest positive integer that consists only of the digit 1 (like 1, 11, 111, 1111, ...) and is divisible by a given positive integer k.

These numbers that contain only the digit 1 are called repunits. For example:

• 1 = 1
• 11 = 11
• 111 = 111
• 1111 = 1111

Your task is to return the length of the smallest such number that is divisible by k.

For instance:

• If k = 3, the smallest repunit divisible by 3 is 111 (since 111 ÷ 3 = 37), so you return 3 (the length of 111)
• If k = 7, the smallest repunit divisible by 7 is 111111 (since 111111 ÷ 7 = 15873), so you return 6

If no repunit can be divisible by k, return -1.

Important Note: The actual number n might be extremely large and not fit in standard integer types, but you only need to return its length, not the number itself.

Intuition

The key insight is that we don't need to store the actual repunit number (which could be massive), but only need to track its remainder when divided by k.

Let's think about how repunits are built:

• 1 = 1
• 11 = 10 + 1 = 1 × 10 + 1
• 111 = 110 + 1 = 11 × 10 + 1
• 1111 = 1110 + 1 = 111 × 10 + 1

Each repunit can be formed by taking the previous repunit, multiplying by 10, and adding 1.

Now, here's the crucial observation: when checking divisibility by k, we only care about remainders. Using modular arithmetic properties:

• (a + b) % k = ((a % k) + (b % k)) % k
• (a × b) % k = ((a % k) × (b % k)) % k

This means instead of computing the full repunit and then checking if it's divisible by k, we can just track the remainder at each step:

• Start with remainder = 1 % k
• For the next repunit: remainder = (remainder × 10 + 1) % k

If the remainder ever becomes 0, we've found a repunit divisible by k.

Why can we be sure to find an answer or determine it's impossible within k iterations? By the Pigeonhole Principle, there are only k possible remainders (0 through k-1). If we haven't found a 0 remainder after k iterations, we'll start seeing repeated remainders, meaning we're in a cycle that doesn't include 0, so no repunit will ever be divisible by k.

For example, if k = 6, the remainders would be: 1, 5, 3, 1, 5, 3... (a repeating cycle), so we return -1. But if k = 3, the remainders would be: 1, 2, 0 (found it at length 3!).

Learn more about Math patterns.

Solution Approach

The implementation follows directly from our intuition about tracking remainders:

1. Initialize the remainder: Start with n = 1 % k, which represents the remainder when the first repunit (1) is divided by k.

2. Iterate up to k times: Use a loop from 1 to k (inclusive) to check each repunit length:

   • If n == 0, we've found a repunit divisible by k, so return the current iteration number i (which represents the length).
   • Otherwise, calculate the remainder for the next repunit using the formula: n = (n * 10 + 1) % k

3. Return -1 if no solution: If we complete all k iterations without finding a remainder of 0, return -1.

Let's trace through an example with k = 3:

• Iteration 1: n = 1 % 3 = 1 (checking repunit "1")
• Since n ≠ 0, continue: n = (1 * 10 + 1) % 3 = 11 % 3 = 2
• Iteration 2: n = 2 (checking repunit "11")
• Since n ≠ 0, continue: n = (2 * 10 + 1) % 3 = 21 % 3 = 0
• Iteration 3: n = 0 (checking repunit "111")
• Since n == 0, return 3

The algorithm uses:

• Time Complexity: O(k) - we iterate at most k times
• Space Complexity: O(1) - we only use a single variable to track the remainder

The modular arithmetic approach elegantly handles the problem constraint that the actual number might not fit in a 64-bit integer, since we never store the full repunit value, only its remainder modulo k.

Example Walkthrough

Let's walk through the solution with k = 7 to find the smallest repunit divisible by 7.

We'll track the remainder at each step instead of the actual repunit number:

Iteration 1: Check repunit "1"

• Current remainder: n = 1 % 7 = 1
• Is n == 0? No, so continue
• Update for next: n = (1 × 10 + 1) % 7 = 11 % 7 = 4

Iteration 2: Check repunit "11"

• Current remainder: n = 4
• Is n == 0? No, so continue
• Update for next: n = (4 × 10 + 1) % 7 = 41 % 7 = 6

Iteration 3: Check repunit "111"

• Current remainder: n = 6
• Is n == 0? No, so continue
• Update for next: n = (6 × 10 + 1) % 7 = 61 % 7 = 5

Iteration 4: Check repunit "1111"

• Current remainder: n = 5
• Is n == 0? No, so continue
• Update for next: n = (5 × 10 + 1) % 7 = 51 % 7 = 2

Iteration 5: Check repunit "11111"

• Current remainder: n = 2
• Is n == 0? No, so continue
• Update for next: n = (2 × 10 + 1) % 7 = 21 % 7 = 0

Iteration 6: Check repunit "111111"

• Current remainder: n = 0
• Is n == 0? Yes! Return 6

The smallest repunit divisible by 7 is "111111" (which equals 111,111), and its length is 6.

Notice how we never stored the actual number 111,111 - we only tracked remainders (1, 4, 6, 5, 2, 0), keeping our calculations small and efficient even when the actual repunit would be enormous.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k)

The algorithm iterates through a loop that runs at most k times (from 1 to k). In each iteration, it performs constant time operations:

• Modulo operation: n == 0 check
• Arithmetic operations: (n * 10 + 1) % k

Since we iterate at most k times with O(1) operations per iteration, the total time complexity is O(k).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variable n to store the current remainder
• Variable i for the loop counter

No additional data structures are used that grow with the input size, so the space complexity is O(1).

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

Common Pitfalls

1. Forgetting Early Termination Cases

A common mistake is not recognizing that certain values of k can never divide any repunit. Specifically, if k is even (divisible by 2) or divisible by 5, no repunit can ever be divisible by k.

Why? Repunits consist only of 1's, so they're always odd numbers. An odd number can never be divisible by an even number. Similarly, for a number to be divisible by 5, it must end in 0 or 5, but repunits only end in 1.

Pitfall Code:

def smallestRepunitDivByK(self, k: int) -> int:
    remainder = 1 % k
    for length in range(1, k + 1):
        if remainder == 0:
            return length
        remainder = (remainder * 10 + 1) % k
    return -1

Solution: Add an early check to immediately return -1 for impossible cases:

def smallestRepunitDivByK(self, k: int) -> int:
    # Early termination for impossible cases
    if k % 2 == 0 or k % 5 == 0:
        return -1
  
    remainder = 1 % k
    for length in range(1, k + 1):
        if remainder == 0:
            return length
        remainder = (remainder * 10 + 1) % k
    return -1

2. Incorrect Loop Bounds

Another pitfall is using incorrect loop bounds, such as starting from 0 or not including k in the range.

Pitfall Code:

def smallestRepunitDivByK(self, k: int) -> int:
    remainder = 1 % k
    for length in range(0, k):  # Wrong: starts from 0, excludes k
        if remainder == 0:
            return length
        remainder = (remainder * 10 + 1) % k
    return -1

Why it's wrong:

• Starting from 0 would return 0 for the first repunit "1" when it's divisible by k
• Excluding k from the range might miss valid solutions

Solution: Use range(1, k + 1) to check lengths from 1 to k inclusive.

3. Checking Remainder After Update

A subtle bug occurs when checking the remainder after updating it within the loop, which causes an off-by-one error in the returned length.

Pitfall Code:

def smallestRepunitDivByK(self, k: int) -> int:
    remainder = 0  # Starting with 0 instead of 1 % k
    for length in range(1, k + 1):
        remainder = (remainder * 10 + 1) % k
        if remainder == 0:  # Checking after update
            return length
    return -1

Solution: Either check the remainder before updating (as in the original solution) or adjust the initialization and return value accordingly to maintain correct length counting.