Skip to content

1064. Smallest Integer Divisible By K

Hash Table Math

Problem - Smallest Integer Divisible By K

Medium

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

Solutions

1
2
3
4
5
6
7
8
class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        n = 1 % k
        for i in range(1, k + 1):
            if n == 0:
                return i
            n = (n * 10 + 1) % k
        return -1

Submission Stats:

  • Runtime: 11 ms (53.34%)
  • Memory: 17.7 MB (76.74%)