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

来源第 129 场周赛 Q2难度中等分数1874

题目描述

给定正整数 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⁵

解法

方法一：数学

思考

构造 \(1,11,111,\ldots\) 直到整除 \(k\)，数值本身会超出整型范围，且 \(k\le 10^5\) 时不能无界地加位数。可整除性只依赖对 \(k\) 的余数。

\((10n+1)\bmod k\) 由 \(n\bmod k\) 决定。余数只有 \(k\) 种，若连续 \(k\) 次都未出现 \(0\)，则以后只会在已见余数中循环，不存在这样的数。

从 \(1\bmod k\) 出发迭代至多 \(k\) 步，第一次余数为 \(0\) 时的步数即位数；否则返回 \(-1\)。

我们注意到，正整数 \(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\) 为给定的正整数。

Python3JavaC++GoTypeScriptRust

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

class Solution {
    public int smallestRepunitDivByK(int k) {
        int n = 1 % k;
        for (int i = 1; i <= k; ++i) {
            if (n == 0) {
                return i;
            }
            n = (n * 10 + 1) % k;
        }
        return -1;
    }
}

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int n = 1 % k;
        for (int i = 1; i <= k; ++i) {
            if (n == 0) {
                return i;
            }
            n = (n * 10 + 1) % k;
        }
        return -1;
    }
};

func smallestRepunitDivByK(k int) int {
    n := 1 % k
    for i := 1; i <= k; i++ {
        if n == 0 {
            return i
        }
        n = (n*10 + 1) % k
    }
    return -1
}

function smallestRepunitDivByK(k: number): number {
    let n = 1 % k;
    for (let i = 1; i <= k; ++i) {
        if (n === 0) {
            return i;
        }
        n = (n * 10 + 1) % k;
    }
    return -1;
}

impl Solution {
    pub fn smallest_repunit_div_by_k(k: i32) -> i32 {
        let mut n = 1 % k;
        for i in 1..=k {
            if n == 0 {
                return i;
            }
            n = (n * 10 + 1) % k;
        }
        -1
    }
}

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

题目描述

解法

方法一：数学

评论