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
这道题说是给了一个正整数K，让找到一个长度最短且只由1组成的正整数N，可以整除K，问最短的长度是多少，若没有，则返回 -1。关于整除的一些性质，博主记得小学就应该学过，比如能被2整除的数字必须是偶数，能被3整除的数字各个位加起来必须能被3整除，能被5整除的数字的末尾数字必须是0或者5。由于N都是由1组成的，所以一定不可能整除2或者5，所以只要K中包含2或者5，直接返回 -1。其实有一个定理，若K不能被2或5整除，则一定有一个长度小于等于K且均由1组成的数，可以整除K。具体的证明博主就不讲了，可以参见论坛上的帖子。这里只要找到那个最短的长度即可，就从1开始试呗，每次乘以 10 再加1，就可以得到下一个数字，但是由于K可能很大，则N就会超出整型数的范围，就算是长整型也不一定 hold 的住，所以不能一直变大，而是每次累加后都要对 K 取余，若余数为0，则直接返回当前长度，若不为0，则用余数乘以 10 再加1，这好像也是用到了余数的一些性质，总之这道题主要就是考察数学知识，跟算法关系不太大，若面试遇到的话，只能自求多福了，参见代码如下：
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/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
