Smallest Integer Divisible by K

main.md

Question

Approach

I build the number consisting only of 1s by tracking its remainder modulo k (so I never construct huge integers). Starting with rem = 0, each step appends a 1 via rem = (rem * 10 + 1) % k. I count steps until rem == 0 and return the count. If k is divisible by 2 or 5 there is no such repunit (every repunit is odd and never divisible by 5), so I return -1. Also, by the pigeonhole principle, if we don't find rem == 0 within k iterations, remainders will cycle and no solution exists, so return -1.

Implementation

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1
        
        rem = 0
        for length in range(1, k + 1):
            rem = (rem * 10 + 1) % k
            if rem == 0:
                return length
        return -1

Complexities

• Time: O(k)
• Space: O(1)