Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Appending a decimal one transforms a number into 10 * number + 1. Divisibility depends only on the remainder modulo k, so the enormous all-ones integer never needs to be stored. There are only k possible remainders; if zero is not reached within k steps, a nonzero remainder repeats and future steps cycle.

Approach

Start with remainder zero. For lengths one through k, update it to (10 * remainder + 1) % k. Return the first length producing zero, which is necessarily the shortest qualifying repunit. Return -1 if the loop ends without success. This also handles divisors containing factors two or five without a separate special case.

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        n = 0

        for i in range(1, k + 1):
            n = (n * 10 + 1) % k
            if n % k == 0:
                return i

        return -1

Complexity analysis

At most k distinct remainders are generated, so time is O(k) and auxiliary space is O(1).