Smallest Integer Divisible by K solution and explanation
Google
TCS
9 more videos on this problem
Smallest Integer Divisible by K - Leetcode 1015 - PythonNeetCodeIO · 18:45 · 7K views
Smallest Integer Divisible by K | Using already Studied Concept | Leetcode 1015 | codestorywithMIKcodestorywithMIK · 19:41 · 7K views
Smallest Integer Divisible by K | Live Coding with Explanation | Leetcode #1015Algorithms Made Easy · 5:41 · 3K views
Smallest Integer Divisible by K | Leetcode 1015 | Live coding session 🔥🔥🔥Coding Decoded · 8:10 · 1K views
Smallest Integer Divisible by K | Leet code 1015 | Theory explained + Python codeSai Anish Malla · 6:06 · 1K views
Daily Leetcode #2065: Nov 25, 2025 - 1015. Smallest Integer Divisible by KProgramming Live with Larry · 6:28 · 566 views
Daily Leetcode #639: Dec 30, 2021 - 1015. Smallest Integer Divisible by KProgramming Live with Larry · 12:58 · 361 views
LeetCode 1015. Smallest Integer Divisible by KHappy Coding · 9:54 · 332 views
1015. Smallest Integer Divisible by K | Leetcode Daily - PythonLeetcode Daily · 9:10 · 217 views
LeetCode 1015 - Smallest Integer Divisible by KLight Of Truth · 11:16 · 177 views
The 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.
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.
def smallestRepunitDivByK(k):
remainder = 0
for length in range(1, k + 1):
remainder = (remainder * 10 + 1) % k
if remainder == 0:
return length
return -1
print(smallestRepunitDivByK(3))public class Solution {
public int smallestRepunitDivByK(int k) {
int remainder = 0;
for (int length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
}
return -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.smallestRepunitDivByK(3));
}
}#include <iostream>
int smallestRepunitDivByK(int k) {
int remainder = 0;
for (int length = 1; length <= k; ++length) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
}
return -1;
}
int main() {
int k = 3;
std::cout << smallestRepunitDivByK(k) << std::endl;
return 0;
}function smallestRepunitDivByK(k) {
let remainder = 0;
for (let length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder === 0) return length;
}
return -1;
}
console.log(smallestRepunitDivByK(3));#include <stdio.h>
int smallestRepunitDivByK(int k) {
int remainder = 0;
for (int length = 1; length <= k; ++length) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
}
return -1;
}
int main() {
int k = 3;
printf("%d\n", smallestRepunitDivByK(k));
return 0;
}using System;
public class Solution {
public int SmallestRepunitDivByK(int k) {
int remainder = 0;
for (int length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.SmallestRepunitDivByK(3));
}
}Using Python's simplicity, we loop up to k to find a valid divisible number with digits only '1'. The remainder pattern is checked, and once a zero remainder is found, the corresponding length is returned.
Time Complexity: O(k).
Space Complexity: O(1).
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.
def smallestRepunitDivByK(k):
remainder = 0
visited = [-1] * k
for length in range(1, k + 1):
remainder = (remainder * 10 + 1) % k
if remainder == 0:
return length
if visited[remainder] != -1:
break
visited[remainder] = length
return -1
print(smallestRepunitDivByK(3))import java.util.Arrays;
public class Solution {
public int smallestRepunitDivByK(int k) {
int remainder = 0;
int[] visited = new int[k];
Arrays.fill(visited, -1);
for (int length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
if (visited[remainder] != -1) break;
visited[remainder] = length;
}
return -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.smallestRepunitDivByK(3));
}
}#include <iostream>
#include <vector>
using namespace std;
int smallestRepunitDivByK(int k) {
int remainder = 0;
vector<int> visited(k, -1);
for (int length = 1; length <= k; ++length) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
if (visited[remainder] != -1) break;
visited[remainder] = length;
}
return -1;
}
int main() {
int k = 3;
cout << smallestRepunitDivByK(k) << endl;
return 0;
}function smallestRepunitDivByK(k) {
let remainder = 0;
let visited = new Array(k).fill(-1);
for (let length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder === 0) return length;
if (visited[remainder] !== -1) break;
visited[remainder] = length;
}
return -1;
}
console.log(smallestRepunitDivByK(3));#include <stdio.h>
#include <string.h>
int smallestRepunitDivByK(int k) {
int remainder = 0;
int visited_remainders[k];
memset(visited_remainders, -1, sizeof(visited_remainders));
for (int length = 1; length <= k; ++length) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
if (visited_remainders[remainder] != -1) break;
visited_remainders[remainder] = length;
}
return -1;
}
int main() {
int k = 3;
printf("%d\n", smallestRepunitDivByK(k));
return 0;
}using System;
public class Solution {
public int SmallestRepunitDivByK(int k) {
int remainder = 0;
int[] visited = new int[k];
Array.Fill(visited, -1);
for (int length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
if (visited[remainder] != -1) break;
visited[remainder] = length;
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.SmallestRepunitDivByK(3));
}
}In Python, tracking of visited remainders facilitates cycle detection and provides an effective exit condition for the iterative search. This pattern identification ensures early exits when needed.
Time Complexity: O(k).
Space Complexity: O(k).
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.
function smallestRepunitDivByK(k: number): number {
let n = 1 % k;
for (let i = 1; i <= k; ++i) {
if (n === 0) {
return i;
}
n = (n * 10 + 1) % k;
}
return -1;
}func smallestRepunitDivByK(k int) int {
n := 1 % k
for i := 1; i <= k; i++ {
if n == 0 {
return i
}
n = (n*10 + 1) % k
}
return -1
}impl Solution {
pub fn smallest_repunit_div_by_k(k: i32) -> i32 {
let mut n = 1 % k;
for i in 1..=k {
if n == 0 {
return i;
}
n = (n * 10 + 1) % k;
}
-1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Modulus Approach | Time Complexity: O(k). |
| Digit Construction and Cycle Detection | Time Complexity: O(k). |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modulus Approach | O(K) | O(1) | Best general solution. Efficient remainder simulation without storing previous states. |
| Digit Construction with Cycle Detection | O(K) | O(K) | Useful when explicitly detecting repeated remainder states or explaining cycle behavior. |
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.