1015. Smallest Integer Divisible by K LeetCode Solution
In this guide, you will get 1015. Smallest Integer Divisible by K LeetCode Solution with the best time and space complexity. The solution to Smallest Integer Divisible by K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(k)
Space Complexity: O(k)
1015. Smallest Integer Divisible by K LeetCode Solution in C++
class Solution {
public:
int smallestRepunitDivByK(int k) {
if (k % 10 != 1 && k % 10 != 3 && k % 10 != 7 && k % 10 != 9)
return -1;
unordered_set<int> seen;
int n = 0;
for (int length = 1; length <= k; ++length) {
n = (n * 10 + 1) % k;
if (n == 0)
return length;
if (seen.contains(n))
return -1;
seen.insert(n);
}
return -1;
}
}; /* code provided by PROGIEZ */
1015. Smallest Integer Divisible by K LeetCode Solution in Java
class Solution {
public int smallestRepunitDivByK(int k) {
if (k % 10 != 1 && k % 10 != 3 && k % 10 != 7 && k % 10 != 9)
return -1;
Set<Integer> seen = new HashSet<>();
int n = 0;
for (int length = 1; length <= k; ++length) {
n = (n * 10 + 1) % k;
if (n == 0)
return length;
if (seen.contains(n))
return -1;
seen.add(n);
}
return -1;
}
} // code provided by PROGIEZ
1015. Smallest Integer Divisible by K LeetCode Solution in Python
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
if k % 10 not in {1, 3, 7, 9}:
return -1
seen = set()
n = 0
for length in range(1, k + 1):
n = (n * 10 + 1) % k
if n == 0:
return length
if n in seen:
return -1
seen.add(n)
return -1 # code by PROGIEZ
