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

这道题说是给了一个正整数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/

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation