1015. Smallest Integer Divisible by K

Time: O(K)

Space: O(K)

Intuition

Use modular arithmetic. Track set of remainders mod K seen so far. If remainder 0 appears in 1*K..n*K substring, we found it.

Algorithm

1For i from 1 to K: num = num*10+1, if num%K==0 return i. Track seen remainders.
2Actually: try 1, 11, 111, ... up to K such numbers. If remainder 0 found, return length.
3Return -1 if K is even or divisible by 5 (since 111...1 never divisible).

Common Pitfalls

•If K is even or multiple of 5: return -1 (111...1 shares no factors with 2 or 5). Otherwise answer exists within K steps by pigeonhole.

1015.cs

// Approach: Simulate repunit growth mod K; if a remainder repeats before reaching 0 it's impossible; early-exit if K ends in even digit or 5.
// Time: O(K) Space: O(K)

public class Solution
{
    public int SmallestRepunitDivByK(int k)
    {
        if (k % 10 != 1 && k % 10 != 3 && k % 10 != 7 && k % 10 != 9)
            return -1;

        HashSet<int> seen = new HashSet<int>();
        int n = 0;

        for (int length = 1; length <= k; ++length)
        {
            n = (n * 10 + 1) % k;
            if (n == 0)
                return length;
            if (seen.Contains(n))
                return -1;
            seen.Add(n);
        }

        return -1;
    }
}

Was this solution helpful?