The "Smallest Integer Divisible by K" interview question asks you to find the length of the smallest positive integer that consists only of the digit '1' and is divisible by k. For example, if k=3, the smallest such number is 111, which has a length of 3. If no such number exists, return -1. This "Smallest Integer Divisible by K coding problem" is a brilliant mix of math and modular arithmetic.
Google asks this to see if a candidate can handle large numbers without actually storing them. A number consisting of many '1's will quickly overflow any standard integer type. The problem tests if you know how to use the property (a * 10 + b) % k == ((a % k) * 10 + b) % k to perform the calculation using only remainders. It also evaluates if you can detect when a number will never be divisible by k.
This problem uses the "Math and Modular Arithmetic interview pattern".
k is a multiple of 2 or 5, no number ending in '1' can ever be divisible by k. Return -1 immediately.rem = 0.len = 1 up to k.rem = (rem * 10 + 1) % k.rem == 0, return len.rem becoming 0, a cycle has occurred, and it will never happen.Let k = 7.
len = 1: rem = (0 * 10 + 1) % 7 = 1.len = 2: rem = (1 * 10 + 1) % 7 = 4.len = 3: rem = (4 * 10 + 1) % 7 = 6.len = 4: rem = (6 * 10 + 1) % 7 = 5.len = 5: rem = (5 * 10 + 1) % 7 = 2.len = 6: rem = (2 * 10 + 1) % 7 = 0.
Result: 6 (The number is 111,111).The most common mistake is attempting to use BigInt or actual numbers, which leads to slow performance or memory issues. Another error is not identifying the k % 2 == 0 or k % 5 == 0 early-exit condition. Some candidates also struggle with the pigeonhole principle logic that explains why the loop only needs to run k times.
Modular arithmetic is the key to handling "too big to store" numbers in coding interviews. Whenever you see a "Smallest Integer Divisible by K interview question", think about how you can use remainders to represent the state of the large number.