给定正整数 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/smallest-integer-divisible-by-k
首先想到的是搞个循环一直除直到得到结果,而对于return -1的情况就要找规律了
- 1 % 5 等于 1
- 11 % 5 等于 1
- 111 % 5 等于 1
- 1111 % 5 等于 1
- 11111 % 5 等于 1
- ...
- 1 % 6 等于 1
- 11 % 6 等于 5
- 111 % 6 等于 3
- 1111 % 6 等于 1
- 11111 /% 6 等于 5
- ...
会发现return -1的数会得到循环节,代码就好写了
class Solution: def smallestRepunitDivByK(self, K: int) -> int: if K%10 in [2,4,5,6,8,10]: return -1//先排掉一些明显的 vis=set() mod=0 for i in range(1,K+1): mod=(mod*10+1)%K if mod in vis: return -1//发现进入循环直接return -1 if mod==0: return i vis.add(mod)