3622. 判断整除性

来源第 459 场周赛 Q1难度简单分数1148

题目描述

给你一个正整数 n。请判断 n 是否可以被以下两值之和整除：

n 的 数字和（即其各个位数之和）。
n 的 数字积（即其各个位数之积）。

如果 n 能被该和整除，返回 true；否则，返回 false。

示例 1：

输入： n = 99

输出： true

解释：

因为 99 可以被其数字和 (9 + 9 = 18) 与数字积 (9 * 9 = 81) 之和 (18 + 81 = 99) 整除，因此输出为 true。

示例 2：

输入： n = 23

输出： false

解释：

因为 23 无法被其数字和 (2 + 3 = 5) 与数字积 (2 * 3 = 6) 之和 (5 + 6 = 11) 整除，因此输出为 false。

提示：

1 <= n <= 10⁶

解法

方法一：模拟

思考

\(n\le 10^6\)，取出各位数字后求和与求积即可。用 \(\textit{divmod}\) 从低位剥离，避免转成字符串。

积的初值须为 \(1\) 而非 \(0\)。判断 \(n\) 是否整除 \(s+p\)。位数为 \(O(\log n)\)。

我们可以遍历整数 \(n\) 的每一位数字，计算出数字和 \(s\) 和数字积 \(p\)。最后判断 \(n\) 是否能被 \(s + p\) 整除。

时间复杂度 \(O(\log n)\)，其中 \(n\) 为整数 \(n\) 的值。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        s, p = 0, 1
        x = n
        while x:
            x, v = divmod(x, 10)
            s += v
            p *= v
        return n % (s + p) == 0

class Solution {
    public boolean checkDivisibility(int n) {
        int s = 0, p = 1;
        int x = n;
        while (x != 0) {
            int v = x % 10;
            x /= 10;
            s += v;
            p *= v;
        }
        return n % (s + p) == 0;
    }
}

class Solution {
public:
    bool checkDivisibility(int n) {
        int s = 0, p = 1;
        int x = n;
        while (x != 0) {
            int v = x % 10;
            x /= 10;
            s += v;
            p *= v;
        }
        return n % (s + p) == 0;
    }
};

func checkDivisibility(n int) bool {
    s, p := 0, 1
    x := n
    for x != 0 {
        v := x % 10
        x /= 10
        s += v
        p *= v
    }
    return n%(s+p) == 0
}

function checkDivisibility(n: number): boolean {
    let [s, p] = [0, 1];
    let x = n;
    while (x !== 0) {
        const v = x % 10;
        x = Math.floor(x / 10);
        s += v;
        p *= v;
    }
    return n % (s + p) === 0;
}

3622. 判断整除性

题目描述

解法

方法一：模拟

评论