1015. 可被 K 整除的最小整数

活到老，学到老。

LC每日一题，参考1015. 可被 K 整除的最小整数，难度分1875。

题目

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

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

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

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。
输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。
输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

解题思路

• 哈希表：枚举余数,碰到相同的余数返回-1。
• 数学优化：排除2和5的倍数的特殊情况后,可以证明其他数必存在答案直接枚举余数。
  • 反证法:假设无解,则不同的1..1必遇到相同的余数即m%k = n%k,即(m-n)%k = 1..10..0%k = (1..1*10..0)%k = 0,因为整除的k不是2和5的倍数,所以必是1..1%k=0,反而得到一个满足题目条件的解假设不成立,所以必有解.

哈希表 2ms

class Solution {
    public int smallestRepunitDivByK(int k) {
        //if(k%2 == 0 || k%5 == 0) return -1;
        int ans = 1,sum = 1%k,pow = (int)Math.pow(10,1);
        int[] hash = new int[k];//sum%k<k 可用HashSet代替8ms 
        while(sum != 0) {
            if(hash[sum]++ > 0) return -1; //!hash.add(sum)
            sum = (sum%k + pow%k)%k;
            ans++;
            pow = pow%k * 10;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(k)，余数个数不会超过k。
• 空间复杂度：O(k)，哈希表空间为k。

数学优化 1ms

class Solution {
    public int smallestRepunitDivByK(int k) {
        if(k%2 == 0 || k%5 == 0) return -1;
        int ans = 1,sum = 1,pow = (int)Math.pow(10,1);
        while(sum % k != 0) {
            sum = sum%k + pow%k;
            ans++;
            pow = pow%k * 10;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(k)。
• 空间复杂度：O(1)。