Smallest Integer Divisible by K — LeetCode 1015 Python Solution

The problem

Given a positive integer k, you need to find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit 1. Return the length of n.

Example

Input

k = 1

Output

1

Explanation

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

Python solution

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

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1015. Smallest Integer Divisible by K is filed here because LeetCode tags it Math, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems