#1015 Smallest Integer Divisible by K - Solution

The goal is to find the length of the smallest number consisting only of digit 1 (a repunit) that is divisible by K. Instead of constructing very large numbers like 1, 11, 111..., we rely on modular arithmetic. At each step, maintain the remainder when the current repunit is divided by K. If the current remainder is r, the next repunit remainder becomes (r * 10 + 1) % K.

Before starting, observe an important constraint: if K is divisible by 2 or 5, no such number exists because repunits always end in 1. Otherwise, repeatedly update the remainder and check when it becomes 0. By the Pigeonhole Principle, at most K different remainders can appear, so the process either finds a valid length or cycles. Some implementations use a hash set to detect repeated remainders, though limiting iterations to K also works.

This approach avoids building huge integers and keeps computations efficient using only remainders.

Approach	Time Complexity	Space Complexity
Iterative remainder simulation	O(K)	O(1)
Remainder tracking with Hash Set	O(K)	O(K)

Solutions (12)

Modulus Approach

This approach leverages the properties of remainders in modular arithmetic. We try to construct a number which consists of only '1's and is divisible by k. We start with the number 1 and find its remainder with k. Then, iteratively, we add another 1 at the right (equivalent to multiply by 10 and add 1) and find the new remainder. We repeat this process until the remainder becomes 0 or a repetition is detected.

If we encounter a remainder that we have seen before, it indicates a cycle, and there is no such number n that will satisfy the condition, hence return -1.

Time Complexity: O(k), as we check for valid remainder up to k possible cases.
Space Complexity: O(1), only a few variables are used.

C C++Java Python C#JavaScript

1#include <iostream>
2
3int smallestRepunitDivByK(int k) {
4    int remainder = 0;
5    for (int length = 1; length <= k; ++length) {
6        remainder = (remainder * 10 + 1) % k;
7        if (remainder == 0) return length;
8    }
9    return -1;
10}
11
12int main() {
    int k = 3;
    std::cout << smallestRepunitDivByK(k) << std::endl;
    return 0;
}

Explanation

This solution is identical to the C version but uses C++ I/O functions. We use modulus operation repeatedly to construct numbers with only '1's and determine their divisibility by k.

Digit Construction and Cycle Detection

This approach still utilizes the modulus technique but introduces a digit construction method. Essentially, instead of just checking the length, we can construct the number step-by-step while simultaneously detecting cycles. The cycle detection ensures we do not repeat remainder calculations unnecessarily, identifying when no solution exists faster.

The goal remains to build a number consisting only of '1's that is divisible by k. The difference here is the emphasis on cycle and digit tracking during construction.

Time Complexity: O(k).
Space Complexity: O(k), due to the use of the visited_remainders array.

C C++Java Python C#JavaScript


public class Solution {
    public int SmallestRepunitDivByK(int k) {
        int remainder = 0;
        int[] visited = new int[k];
        Array.Fill(visited, -1);
        for (int length = 1; length <= k; length++) {
            remainder = (remainder * 10 + 1) % k;
            if (remainder == 0) return length;
            if (visited[remainder] != -1) break;
            visited[remainder] = length;
        }
        return -1;
    }
    public static void Main(string[] args) {
        Solution solution = new Solution();
        Console.WriteLine(solution.SmallestRepunitDivByK(3));
    }
}