Skip to main content
Talentd

Smallest Integer Divisible by K - Solution & Explanation

MediumHash TableMath20 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

 

Example 1:

Input: k = 1
Output: 1
Explanation: The smallest answer is n = 1, which has length 1.

Example 2:

Input: k = 2
Output: -1
Explanation: There is no such positive integer n divisible by 2.

Example 3:

Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.

 

Constraints:

  • 1 <= k <= 105

Approach Overview

Problem Overview: Given an integer K, return the length of the smallest positive integer composed only of the digit 1 that is divisible by K. The number can be extremely large, so constructing the full integer directly is not feasible. The key is to work with remainders instead of the actual number.

Approach 1: Modulus Approach (O(K) time, O(1) space)

The integer consisting of only 1s can be built incrementally using remainders. Instead of forming the full number, keep track of the remainder when the current number is divided by K. If the current remainder is r, the next number formed by appending 1 becomes (r * 10 + 1) % K. Continue this process until the remainder becomes 0, which means the constructed number is divisible by K. If K is divisible by 2 or 5, such a number cannot exist because numbers made of only 1s always end with digit 1. This approach relies on modular arithmetic from math and avoids storing large integers. The process runs at most K iterations since there are only K possible remainders.

Approach 2: Digit Construction and Cycle Detection (O(K) time, O(K) space)

This approach also builds the number conceptually using remainder updates, but explicitly tracks previously seen remainders using a set or hash table. Each step computes remainder = (remainder * 10 + 1) % K. If the remainder becomes 0, the current length is the answer. If a remainder repeats, the sequence has entered a cycle and it is impossible to reach 0. Tracking remainders guarantees termination and provides a clear explanation of why the algorithm works: repeated states imply infinite repetition of the same remainder sequence.

The key insight behind both approaches is that the remainder uniquely determines the future sequence of digits. Since only K distinct remainders exist, the process must either reach 0 or repeat a previous remainder. This transforms what appears to be a big integer construction problem into a manageable modular arithmetic simulation.

Recommended for interviews: The modulus-based remainder simulation is the expected solution. It shows comfort with modular arithmetic and avoids unnecessary memory. Mentioning the cycle-detection idea demonstrates deeper reasoning about remainder states and connects naturally to hash table techniques used to detect repeated states.

Approach 1: 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.

We start with a remainder of 0 and iterate up to k times, constructing the number step-by-step by updating the remainder. The formula remainder = (remainder * 10 + 1) % k helps us construct the number in the form of '111...1' without actually building this number explicitly. If we find a remainder of 0, the length of such a number is returned. If a cycle is detected, meaning all possible remainders are tried without success, -1 is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: 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.

Here, we include an additional array to track each remainder used. A cycle is detected if the same remainder appears twice before finding a solution. Using visited_remainders, we store each state and verify conditions for possible cycles. This strategy optimizes cycle detection and avoids unnecessary computations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: Mathematics

We observe that the positive integer n starts with an initial value of 1, and each time it is multiplied by 10 and then 1 is added, i.e., n = n times 10 + 1. Since (n times 10 + 1) bmod k = ((n bmod k) times 10 + 1) bmod k, we can determine whether n is divisible by k by calculating n bmod k.

We start from n = 1 and calculate n bmod k each time until n bmod k = 0. At this point, n is the smallest positive integer we are looking for, and its length is the number of digits in n. Otherwise, we update n = (n times 10 + 1) bmod k. If after looping k times we still haven't found n bmod k = 0, it means no such n exists, and we return -1.

The time complexity is O(k) and the space complexity is O(1), where k is the given positive integer.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Modulus Approach

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.

Digit Construction and Cycle Detection

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

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Modulus ApproachO(K)O(1)Best general solution. Efficient remainder simulation without storing previous states.
Digit Construction with Cycle DetectionO(K)O(K)Useful when explicitly detecting repeated remainder states or explaining cycle behavior.

Video Solution

Smallest Integer Divisible by K - Leetcode 1015 - Python • NeetCodeIO • 7,918 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Integer Divisible by K easy or hard?
This problem is generally classified as Medium difficulty. The challenge comes from recognizing that directly constructing the integer is impractical and that the problem can be solved using modular arithmetic and remainder tracking.
Smallest Integer Divisible by K Python/Java solution
In Python or Java, the implementation tracks a remainder variable and iteratively updates it using (remainder * 10 + 1) % K. The loop continues until the remainder becomes zero or a cycle is detected. The algorithm runs in O(K) time and avoids constructing very large integers.
How to solve Smallest Integer Divisible by K in O(K)?
Maintain a running remainder instead of constructing the full number. Start with remainder = 1 % K, then repeatedly update remainder = (remainder * 10 + 1) % K. Count how many digits are appended. When the remainder becomes 0, that count is the length of the smallest valid number.
What is the best approach for Smallest Integer Divisible by K?
The modulus remainder simulation is the best approach. Instead of constructing a huge number made of repeated '1' digits, track the remainder using the formula (remainder * 10 + 1) % K. The algorithm stops when the remainder becomes 0. This runs in O(K) time and O(1) space.
Is Smallest Integer Divisible by K asked at Google/Amazon/Meta?
Problems involving modular arithmetic, remainder cycles, and number construction appear in interviews at large tech companies. Variants of this problem have shown up in coding rounds because they test mathematical reasoning and efficient state tracking.
What data structure is used in Smallest Integer Divisible by K?
The core solution relies on modular arithmetic from math. Some implementations use a hash set to store previously seen remainders and detect cycles, which brings in the hash table data structure.
What is the time complexity of Smallest Integer Divisible by K?
The optimal solution runs in O(K) time because there are only K possible remainders when dividing by K. Each step computes a new remainder using modular arithmetic. Space complexity can be O(1) if you do not store previous remainders, or O(K) if cycle detection uses a hash set.

Ready to solve this problem?

Practice Smallest Integer Divisible by K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters