How do I approach the Smallest Integer Divisible by K problem?

Use modular arithmetic to track remainders and check for cycles. You only need to track the remainder modulo k rather than constructing the number directly.

What if no solution exists for a given k?

If the remainder starts repeating without finding a solution, return -1, indicating no such number exists.

Can the solution handle very large values of k?

Yes, the solution efficiently handles large k values by working with remainders modulo k instead of large numbers.

What is the time complexity of the solution?

The time complexity is O(K) since we only need to track up to K different remainders during the process.

What are common mistakes when solving this problem?

Common mistakes include trying to generate large numbers directly, not detecting cycles, or misunderstanding the importance of remainders modulo k.

#1015

Medium

auto_awesome哈希·数学

LeetCode 题解工作台

可被 K 整除的最小整数

给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最小正整数 n 的长度。返回 n 的长度。如果不存在这样的 n ，就返回-1。注意： n 可能不符合 64 位带符号整数。示例 1：输入： k = 1 输出： 1 解释：最小的答案是 n = 1，其长度为 1。示例 2…

哈希表数学

题目描述

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

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

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

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。

示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

提示：

1 <= k <= 10⁵

lightbulb

解题思路

方法一：数学

我们注意到，正整数 $n$ 初始值为 $1$ ，每次乘以 $10$ 后再加 $1$ ，即 $n = n \times 10 + 1$ ，而 $(n \times 10 + 1) \bmod k = ((n \bmod k) \times 10 + 1) \bmod k$ ，因此我们可以通过计算 $n \bmod k$ 来判断 $n$ 是否能被 $k$ 整除。

我们从 $n = 1$ 开始，每次计算 $n \bmod k$ ，直到 $n \bmod k = 0$ ，此时 $n$ 就是我们要求的最小正整数，其长度即为 $n$ 的位数。否则，我们更新 $n = (n \times 10 + 1) \bmod k$ 。如果循环 $k$ 次后，仍然没有找到 $n \bmod k = 0$ ，则说明不存在这样的 $n$ ，返回 $-1$ 。

时间复杂度 $O(k)$ ，空间复杂度 $O(1)$ 。其中 $k$ 为给定的正整数。

1

2

3

4

5

6

7

8

9

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        n = 1 % k
        for i in range(1, k + 1):
            if n == 0:
                return i
            n = (n * 10 + 1) % k
        return -1

speed

复杂度分析

指标	值
时间	\mathcal{O}(K)
空间	\mathcal{O}(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of modular arithmetic.
question_mark
The candidate suggests cycle detection or early stopping to optimize the process.
question_mark
The candidate is aware of large number constraints and handles them with remainders.

warning

常见陷阱

外企场景

error
Failing to handle cases where the remainder starts repeating, which would indicate a cycle and no solution.
error
Not realizing that constructing large numbers isn't necessary; only the remainder modulo k matters.
error
Misunderstanding the problem and attempting to generate large numbers directly instead of focusing on modular properties.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if k is very large (greater than 10^5)?
arrow_right_alt
How does this approach scale if we need to handle multiple test cases efficiently?
arrow_right_alt
What if we extend the problem to include numbers with only certain digits, not just '1'?

help

常见问题

外企场景

继续练习

#996 平方数组的数目 #970 强整数 #963 最小面积矩形 II