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.
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.
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.
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.
Time Complexity: O(k).
Space Complexity: O(k), due to the use of the visited_remainders array.
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.
| Approach | Complexity |
|---|---|
| Modulus Approach | Time Complexity: O(k), as we check for valid remainder up to k possible cases. |
| Digit Construction and Cycle Detection | Time Complexity: O(k). |
| Mathematics | — |
| 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. |
Smallest Integer Divisible by K - Leetcode 1015 - Python • NeetCodeIO • 7,546 views views
Watch 9 more video solutions →Practice Smallest Integer Divisible by K with our built-in code editor and test cases.
Practice on FleetCode