Description
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
Solution 1: 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 × 10 + 1. Since (n × 10 + 1) \bmod k = ((n \bmod k) × 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 × 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.
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(code-box)
