Smallest Integer Divisible by K

Medium
1284.

Smallest Integer Divisible by K

Smallest Integer Divisible by K is a medium coding problem on hash table, math and number theory, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} k
 * @return {number}
 */
var smallestRepunitDivByK = function(k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    You only care whether n is divisible by k, so keep n mod k instead of n. Appending a digit 1 turns remainder r into (10r + 1) mod k.

  2. Hint 2

    There are only k possible remainders. If none of the first k lengths gives remainder 0, the remainders are cycling and never will.

  3. Hint 3

    If k is 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

  1. If k is divisible by 2 or 5, return -1.
  2. Set r = 0. For length from 1 to k: r = (r * 10 + 1) % k; if r == 0, return length.
  3. 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 + 1 stays 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 -1

Java

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