Smallest Integer Divisible by K 可被 K 整除的最小整数

问题描述：

问题
给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的【最小正整数】 n 的长度。

返回 n 的长度。如果不存在这样的 n ，就返回-1。

注意： n 不符合 64 位带符号整数。

分析

就是寻找一个 n，这个n需要满足几个条件
1 n是一个整数
2 n%k == 0
3 n 的数位只包含 1
暴力的思路就是枚举所有的可能n，即 1,11,111,1111,1…1.
然后对于每个数进行条件123的检测。因为在这个过程中，每个枚举的数都是位数逐渐增加的，所以只要找到第一个就可以。
整体思路很OK，然而怎么可能那么简单。只能说上面的思路对，又不完全的对。
如果存在一种k，任何一个枚举的n都不能满足n%k==0,那么上面的思路，不停的扩展枚举数的位数，就是无意义的，而且无法退出，因为永远都无法找到这样的n。
此外，问题中还提示，n 不符合64位有符合整数。原文是n may not fit in a 64-bit signed integer.
这意思就是说，可能n比2^64还大，这样的数以目前的int，long都无法处理。
所以新的问题就是对于k来说，是否存在符合上面条件的n。对于k=2,很明显2的倍数尾数必然是偶数24680，所以绝对不可能有这样的n，可以返回-1.
类似的还有5，其倍数也是05结尾。
回到之前的暴力，当n=1,长度为1,如果 n mod k = remainder1 =0,那么结果就是1.如果 remainder1!=0,那么就需要扩展得到n’= 10n +1,即11 ，11 mod k = remainder2.如果 remainder2=0，也可以说明结果是2，否则就需要继续扩展。
这里有个mod，就是模计算，求余用的。你会不会想到些什么。
(a+b)%m = (a%m+b%m)%m
(ab)%m = ((a%m)(b%m))%m
对于 11 mod k ==> (10+1)mod k,
即 n’ mod k ==>(10n +1 ) mod k
==> [(10n) mod k + (1 mod k) ] mod k
==> [ (10 mod k)*( n mod k ) + (1 mod k)] mod k

==> [ (10 mod k)*remainderOld + (1 mod k)] mod k
==> [ (10 mod k)(remainderOld mod k) + (1 mod k)] mod k
==> [ (10remainderOld mod k) + 1] mod k
==> [ (10*remainderOld) + 1] mod k
== remainderNew
$==> [(10 n) m o d k + (1 m o d k)] m o d k ==> [(10 m o d k) * (nm o d k) + (1 m o d k)] m o d k$

$==> [(10 m o d k) * re main d er Ol d + (1 m o d k)] m o d k ==> [(10 m o d k) * (re main d er Ol d m o d k) + (1 m o d k)] m o d k$

$==> [(10 * re main d er Ol d m o d k) + 1] m o d k ==> [(10 * re main d er Ol d) + 1] m o d k == re main d er N e w$

到此，前一个n和后一个n 关于k就有一个关系。
这样每一次都可以通过前一个remainder,计算得到当前n’的remainder。remainder有什么用，你品。
remainder的范围就是[0,k-1],所以使用set记录，当set出现重复的remainder，就说明继续计算也无法得到新的remainder，可以结束，返回-1.

时间复杂度 O(k)
空间复杂度： O(k)

代码

class Solution {public int smallestRepunitDivByK(int k) {int resid = 1 % k, len = 1; // resid为余数，len为数字长度，初始值为1Set<Integer> set = new HashSet<Integer>(); // 创建一个无序集合，用于存储余数set.add(resid); // 插入余数1while (resid != 0) { // 当余数为0时退出循环resid = (resid * 10 + 1) % k; // 计算下一个余数len++; // 数字长度+1if (set.contains(resid)) { // 如果余数重复出现，则无解return -1;}set.add(resid); // 将余数插入集合}return len; // 返回数字长度 }
}