Watch 10 video solutions for Smallest Integer Divisible by K, a medium level problem involving Hash Table, Math. This walkthrough by NeetCodeIO has 7,546 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105Problem 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 | 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. |