Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1015.html
1015. Smallest Integer Divisible by K
Level
Medium
Description
Given a positive integer K
, you need find 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.
Example 1:
Input: 1
Output: 1
Explanation: The smallest answer is N = 1, which has length 1.
Example 2:
Input: 2
Output: -1
Explanation: There is no such positive integer N divisible by 2.
Example 3:
Input: 3
Output: 3
Explanation: The smallest answer is N = 111, which has length 3.
Note:
1 <= K <= 10^5
Solution
If K
is a multiple of 2 or 5, then any number divisible by K
can’t end with 1, so return -1
.
Otherwise, each time append a 1 to the current number (which is initially 0) and check whether the new number is divisible by K
. Use modulo operation to avoid overflow.
-
class Solution { public int smallestRepunitDivByK(int K) { if (K % 2 == 0 || K % 5 == 0) return -1; int value = 1; int length = 1; while (value % K != 0) { value = value % K * 10 + 1; length++; } return length; } }
-
// OJ: https://leetcode.com/problems/smallest-integer-divisible-by-k/ // Time: O(K) // Space: O(K) class Solution { public: int smallestRepunitDivByK(int k) { unordered_set<int> s; for (int n = 1 % k, len = 1; true; n = (n * 10 + 1) % k, ++len) { if (n == 0) return len; if (s.count(n)) return -1; s.insert(n); } } };
-
# 1015. Smallest Integer Divisible by K # https://leetcode.com/problems/smallest-integer-divisible-by-k/ class Solution: def smallestRepunitDivByK(self, k: int) -> int: if k % 2 == 0 and k % 5 == 0: return -1 mod_set = set() prev = 0 for i in range(1, k + 1): prev = (prev * 10 + 1) % k if prev == 0: return i if prev in mod_set: return -1 mod_set.add(prev) return -1
-
func smallestRepunitDivByK(k int) int { n := 1 % k for i := 1; i <= k; i++ { if n == 0 { return i } n = (n*10 + 1) % k } return -1 }
-
function smallestRepunitDivByK(k: number): number { let n = 1 % k; for (let i = 1; i <= k; ++i) { if (n === 0) { return i; } n = (n * 10 + 1) % k; } return -1; }