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

``````class Solution {
public:
int smallestRepunitDivByK(int K) {
if (K % 2 == 0 || K % 5 == 0) return -1;
int r = 0;
for (int i = 1; i <= K; ++i) {
r = (r * 10 + 1) % K;
if (r == 0) return i;
}
return -1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1015

https://leetcode.com/problems/smallest-integer-divisible-by-k/

https://leetcode.com/problems/smallest-integer-divisible-by-k/discuss/260852/JavaC%2B%2BPython-O(1)-Space-with-Proves-of-Pigeon-Holes

https://leetcode.com/problems/smallest-integer-divisible-by-k/discuss/260916/Proof%3A-we-only-need-to-consider-the-first-K-candidates-in-1-11-111-1111-...

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation