Smallest Integer Divisible by K — Problem & Solution
Smallest Integer Divisible by K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Smallest Integer Divisible by K is a medium coding problem on hash table, math and number theory, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Hash Table, Math, Number Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a positive integer k, find the smallest positive integer n that is divisible by k and whose decimal digits are all 1 (like 1, 11, 111, …).
Return the number of digits of n, or -1 if no such n exists.
Note that n itself can be far too large for any integer type — only its length is returned.
Example 1
Input: k = 1
Output: 1
Explanation: n = 1.
Example 2
Input: k = 2
Output: -1
Explanation: Every number made of ones is odd.
Example 3
Input: k = 3
Output: 3
Explanation: n = 111 = 3 × 37.
Constraints
1 <= k <= 10^5
Hints for Smallest Integer Divisible by K
Hint 1
You only care whether
nis divisible byk, so keepn mod kinstead ofn. Appending a digit 1 turns remainderrinto(10r + 1) mod k.Hint 2
There are only
kpossible remainders. If none of the firstklengths gives remainder 0, the remainders are cycling and never will.Hint 3
If
kis divisible by 2 or 5 the answer is immediately -1, since every all-ones number ends in 1.
How to solve Smallest Integer Divisible by K
Track the remainder of the all-ones number modulo k as it grows by one digit; by the pigeonhole principle, k steps either hit remainder 0 or never will.
Approach
- If
kis divisible by 2 or 5, return -1. - Set
r = 0. Forlengthfrom 1 tok:r = (r * 10 + 1) % k; ifr == 0, returnlength. - Return -1 (not reached when
gcd(k, 10) = 1).
Why it works
The remainder of the length-L repunit determines the next one, so the sequence of remainders is eventually periodic. When gcd(k, 10) = 1 the step r → 10r + 1 is a bijection modulo k, so the sequence is purely periodic and must return to its starting value 0 within k steps — the answer always exists and is at most k. When 2 or 5 divides k, any multiple of k ends in an even digit or in 0 or 5, never in 1.
Complexity
- Time —
O(k) - Space —
O(1)
Pitfalls
- Building the actual number overflows after 10 digits; carry only the remainder.
- Without the 2/5 check you need a cycle detector (or the
k-step bound) to stop. r * 10 + 1stays below 10^6 here, but keep the reduction inside the loop.
Reference solution
Python
def smallestRepunitDivByK(k: int) -> int:
if k % 2 == 0 or k % 5 == 0:
return -1
r = 0
for length in range(1, k + 1):
r = (r * 10 + 1) % k
if r == 0:
return length
return -1Java
public static int smallestRepunitDivByK(int k) {
if (k % 2 == 0 || k % 5 == 0) return -1;
int r = 0;
for (int length = 1; length <= k; length++) {
r = (r * 10 + 1) % k;
if (r == 0) return length;
}
return -1;
}C++
int smallestRepunitDivByK(int k) {
if (k % 2 == 0 || k % 5 == 0) return -1;
int r = 0;
for (int length = 1; length <= k; length++) {
r = (r * 10 + 1) % k;
if (r == 0) return length;
}
return -1;
}JavaScript
var smallestRepunitDivByK = function(k) {
if (k % 2 === 0 || k % 5 === 0) return -1;
var r = 0;
for (var length = 1; length <= k; length++) {
r = (r * 10 + 1) % k;
if (r === 0) return length;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets