{x}
blog image

Smallest Integer Divisible by K

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

Solution Explanation for Smallest Integer Divisible by K

This problem asks to find the length of the smallest positive integer n that is divisible by k and consists only of the digit 1. The solution leverages the concept of modular arithmetic to efficiently solve this problem without actually constructing the large integer n.

Approach:

The core idea is to iteratively build the number n digit by digit (where each digit is 1). Instead of storing the entire number n, we only track its remainder when divided by k. This is because if n is divisible by k, then its remainder when divided by k will be 0.

The algorithm works as follows:

  1. Initialization: Start with n = 1 % k. This gives the remainder of 1 when divided by k.
  2. Iteration: In each iteration, we simulate adding another digit '1' to n. This is done by multiplying the current remainder n by 10 and adding 1, then taking the modulo with k: n = (n * 10 + 1) % k. This efficiently updates the remainder without needing to handle potentially very large numbers.
  3. Check for Divisibility: After each iteration, we check if the remainder n is 0. If it is, then the current length i (the number of iterations) represents the length of the smallest integer n divisible by k. We return i.
  4. No Solution: If the loop completes without finding a remainder of 0, it means no such integer n exists, and we return -1.

Time Complexity Analysis:

The algorithm iterates at most k times. Therefore, the time complexity is O(k), which is linear in the value of k.

Space Complexity Analysis:

The algorithm uses only a few constant extra variables (n, i). Therefore, the space complexity is O(1), which is constant.

Code Explanations (Python as Example):

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        n = 1 % k  # Initialize remainder
        for i in range(1, k + 1):  # Iterate up to k (worst case)
            if n == 0:  # Check if remainder is 0
                return i  # Found solution: return length
            n = (n * 10 + 1) % k  # Simulate adding '1' and update remainder
        return -1  # No solution found

The other languages (Java, C++, Go, TypeScript) follow the same logic, with minor syntax differences reflecting the specific language conventions. The core algorithm remains identical across all implementations.