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

题目地址(1015. 可被 K 整除的最小整数)

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

题目描述

给定正整数 K,你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N。

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

 

示例 1:

输入:1
输出:1
解释:最小的答案是 N = 1,其长度为 1。
示例 2:

输入:2
输出:-1
解释:不存在可被 2 整除的正整数 N 。
示例 3:

输入:3
输出:3
解释:最小的答案是 N = 111,其长度为 3。
 

提示:

1 <= K <= 10^5

前置知识

  • 循环节

公司

  • 暂无

思路

这道题是说给定一个 K 值,能否找到一个形如 1,11,111,1111 。。。 的数字 n,使得 n % K == 0,并要求 n 尽可能地小。

由于题目要找一个尽可能小的 n ,那么我们可以从小到大进行枚举,直到找到这样的一个 n 值即可。即从 1,11,111,1111 。。。 这样一直除下去,直到碰到可以整除的,我们返回即可。

但是如果这个数字根本就无法整除怎么办?没错,我们会无限循环下去。那么我们应该在什么时刻跳出循环返回 - 1 (表示不能整除)呢?

比如 k = 2 来说我们的算法过程如下:

  • 1 // 2 等于 1

  • 11 // 2 等于 1

  • 111 // 2 等于 1

  • ...

如果 k = 6 算法过程如下:

  • 1 // 6 等于 1

  • 11 // 6 等于 5

  • 111 // 6 等于 3

  • 1111 // 6 等于 1

  • 11111 // 6 等于 5

  • ...

通过观察我们发现不断整除的过程,会陷入无限循环,对于 2 来说,其循环节就是 1。对于 6 来说,其循环节来说就是 153。而且由于我们的分母是 6,也就是说余数的可能性一共只有六种情况 0,1,2,3,4,5。

上面是感性的认识, 接下来我们从数学上予以证明。

上面的算法用公式来表示就是mod = (10 * mod + 1) % K,其中 mode 为 111xxx111 模 k 的值。假如出现了相同的数,我们可以肯定之后会无限循环。比如 153 之后出现了 1,我们可以肯定之后一定是 35。。。 这是因为我们的 mod 只是和前一个 mod 有关。换句话说就是上面的公式mod = (10 * mod + 1) % K是一个纯函数,相同的输入输出总是相同的。(也就是说 x mod k 后是 y,下次再碰到 x,继续 mod k 一定还是 y,然后无限循环下去)。

关键点解析

  • 数学(无限循环与循环节)

代码

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        if K % 10 in [2, 4, 5, 6, 8]:
            return - 1
        seen = set()
        mod = 0
        for i in range(1, K + 1):
            mod = (mod * 10 + 1) % K
            if mod in seen:
                return -1
            if mod == 0:
                return ix
            seen.add(mod)

相关题目

最后更新于