#1015

Medium

LeetCode Problem Workspace

Smallest Integer Divisible by K

Find the length of the smallest positive integer divisible by k that consists only of the digit '1'.

Problem Statement

Given a positive integer k, find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit '1'. If no such integer exists, return -1.

Note that n may not fit within a 64-bit signed integer. The problem requires finding the length of n rather than constructing it entirely.

Examples

Example 1

Input: k = 1

Output: 1

The smallest answer is n = 1, which has length 1.

Example 2

Input: k = 2

Output: -1

There is no such positive integer n divisible by 2.

Example 3

Input: k = 3

Output: 3

The smallest answer is n = 111, which has length 3.

Constraints

1 <= k <= 105

Solution Approach

Modular Arithmetic Approach

The solution involves calculating remainders of numbers consisting only of the digit '1' modulo k. Starting with the number '1', we append another '1' to the number and compute its remainder modulo k. If at any point the remainder equals zero, the corresponding length of n is the answer.

Efficient Remainder Tracking

Instead of constructing large numbers, track only the remainder when divided by k. This allows us to efficiently check if the constructed number is divisible by k without explicitly building large integers.

Cycle Detection

If the remainder begins repeating, it means we’ve entered a cycle without finding a valid solution. This indicates that there is no such integer n divisible by k.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(K)
Space	\mathcal{O}(1)

The time complexity is O(K) because we only need to track up to K different remainders. The space complexity is O(1) since we only store the current remainder during the process.

What Interviewers Usually Probe

The candidate demonstrates understanding of modular arithmetic.
The candidate suggests cycle detection or early stopping to optimize the process.
The candidate is aware of large number constraints and handles them with remainders.

Common Pitfalls or Variants

Common pitfalls

Failing to handle cases where the remainder starts repeating, which would indicate a cycle and no solution.
Not realizing that constructing large numbers isn't necessary; only the remainder modulo k matters.
Misunderstanding the problem and attempting to generate large numbers directly instead of focusing on modular properties.

Follow-up variants

What if k is very large (greater than 10^5)?
How does this approach scale if we need to handle multiple test cases efficiently?
What if we extend the problem to include numbers with only certain digits, not just '1'?

FAQ

How do I approach the Smallest Integer Divisible by K problem?

Use modular arithmetic to track remainders and check for cycles. You only need to track the remainder modulo k rather than constructing the number directly.

What if no solution exists for a given k?

If the remainder starts repeating without finding a solution, return -1, indicating no such number exists.

Can the solution handle very large values of k?

Yes, the solution efficiently handles large k values by working with remainders modulo k instead of large numbers.

What is the time complexity of the solution?

The time complexity is O(K) since we only need to track up to K different remainders during the process.

What are common mistakes when solving this problem?

Common mistakes include trying to generate large numbers directly, not detecting cycles, or misunderstanding the importance of remainders modulo k.

terminal

Solution

Solution 1: Mathematics

We observe that the positive integer $n$ starts with an initial value of $1$, and each time it is multiplied by $10$ and then $1$ is added, i.e., $n = n \times 10 + 1$. Since $(n \times 10 + 1) \bmod k = ((n \bmod k) \times 10 + 1) \bmod k$, we can determine whether $n$ is divisible by $k$ by calculating $n \bmod k$.

1

2

3

4

5

6

7

8

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        n = 1 % k
        for i in range(1, k + 1):
            if n == 0:
                return i
            n = (n * 10 + 1) % k
        return -1

Continue Practicing

#996 number of squareful arrays #970 powerful integers #963 minimum area rectangle ii