1015. Smallest Integer Divisible by K
mediumFind the length of the smallest integer consisting only of digit 1 (a 'repunit') that is divisible by k, or -1 if no such number exists. A clever modular-arithmetic problem hiding inside a digit-construction puzzle.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
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. If there is no such n, return -1. Note: n may not fit in a 64-bit signed integer.
Constraints
1 <= k <= 10^5
Examples
Example 1
k = 11Explanation: The smallest answer is n = 1, which has length 1.
Example 2
k = 2-1Explanation: There is no such positive integer n divisible by 2.
Example 3
k = 33Explanation: The smallest answer is n = 111, which has length 3.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
If k is even or k is divisible by 5, the answer is -1 — any repunit (1, 11, 111, ...) ends in 1, so its last digit is 1, not 0 or even.
Hint 2
Otherwise, do the math modulo k. Build repunits incrementally: r_1 = 1; r_{n+1} = (r_n * 10 + 1) mod k.
Hint 3
Stop the first time r_n == 0. Return n.
Hint 4
By the pigeonhole principle, if k is coprime to 10, the sequence cycles through at most k different residues — so the answer is at most k.
Solution approach
Reveal approach
Two early-exit cases: if k % 2 == 0 or k % 5 == 0, return -1 — repunits end in 1, and any multiple of 2 or 5 cannot end in 1 (it ends in 0, 2, 4, 5, 6, or 8). Otherwise simulate the repunit-mod-k sequence: r = 0, length = 0. Loop: length++; r = (r * 10 + 1) % k. If r == 0, return length. By pigeonhole the residues must repeat within k iterations, but the gcd-with-10 = 1 condition guarantees one of them is 0 (the repunit-cyclic-number theorem). So the loop terminates within k steps and the answer is at most k. O(k) time, O(1) space — never materialize the actual repunit (which would overflow).
Complexity
- Time
- O(k)
- Space
- O(1)
Related patterns
- math
- number-theory
- hash-set
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
Practice these live with InterviewChamp.AI
Drill Smallest Integer Divisible by K and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →