1015

1015. 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

Companies:
Google

Related Topics:
Hash Table, Math

Solution 1.

// OJ: https://leetcode.com/problems/smallest-integer-divisible-by-k/
// Author: github.com/lzl124631x
// 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);
        }
    }
};

Or using the Pigeonhole Principle

// OJ: https://leetcode.com/problems/smallest-integer-divisible-by-k/
// Author: github.com/lzl124631x
// Time: O(K)
// Space: O(1)
class Solution {
public:
    int smallestRepunitDivByK(int k) {
        for (int n = 1 % k, len = 1; len <= k; n = (n * 10 + 1) % k, ++len) {
            if (n == 0) return len;
        }
        return -1;
    }
};