Easy

题目描述

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

  • n 的数字和（各位数字的和）
  • n 的数字积（各位数字的积）

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

示例 1：

输入：n = 99
输出：true
解释：99 能被其数字和 (9 + 9 = 18) 与数字积 (9 * 9 = 81) 的和 (总计 99) 整除，所以输出为 true。

示例 2：

输入：n = 23
输出：false
解释：23 不能被其数字和 (2 + 3 = 5) 与数字积 (2 * 3 = 6) 的和 (总计 11) 整除，所以输出为 false。

提示：

  • 1 <= n <= 10^6

解题思路

这道题的核心思路非常直接：

  1. 提取数字的各位数字：遍历数字 n 的每一位，可以通过取模运算 n % 10 得到最后一位，然后整除 n /= 10 移除最后一位。

  2. 计算数字和与数字积：在遍历过程中同时累加得到数字和，累乘得到数字积。

  3. 检查整除性：计算数字和与数字积的和，然后检查原数字 n 是否能被这个和整除。

需要注意的边界情况：

  • 当数字中包含 0 时，数字积会变成 0，此时数字和与数字积的和就等于数字和本身
  • 由于 n 是正整数且最大为 10^6，不会出现除零的情况

算法步骤：

  1. 保存原始的 n 值
  2. 逐位提取数字，同时计算数字和与数字积
  3. 返回 原始n % (数字和 + 数字积) == 0 的结果

时间复杂度为 O(log n)，因为需要遍历数字的每一位；空间复杂度为 O(1)。

代码实现

class Solution {
public:
    bool checkDivisibility(int n) {
        int original = n;
        int digitSum = 0;
        int digitProduct = 1;
        
        while (n > 0) {
            int digit = n % 10;
            digitSum += digit;
            digitProduct *= digit;
            n /= 10;
        }
        
        return original % (digitSum + digitProduct) == 0;
    }
};

class Solution:
    def checkDivisibility(self, n: int) -> bool:
        original = n
        digit_sum = 0
        digit_product = 1
        
        while n > 0:
            digit = n % 10
            digit_sum += digit
            digit_product *= digit
            n //= 10
        
        return original % (digit_sum + digit_product) == 0

public class Solution {
    public bool CheckDivisibility(int n) {
        int original = n;
        int digitSum = 0;
        int digitProduct = 1;
        
        while (n > 0) {
            int digit = n % 10;
            digitSum += digit;
            digitProduct *= digit;
            n /= 10;
        }
        
        return original % (digitSum + digitProduct) == 0;
    }
}

/**
 * @param {number} n
 * @return {boolean}
 */
var checkDivisibility = function(n) {
    let digitSum = 0;
    let digitProduct = 1;
    let temp = n;
    
    while (temp > 0) {
        let digit = temp % 10;
        digitSum += digit;
        digitProduct *= digit;
        temp = Math.floor(temp / 10);
    }
    
    return n % (digitSum + digitProduct) === 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log n) - 需要遍历数字的每一位，位数为 log₁₀(n)
空间复杂度O(1) - 只使用常数个变量存储中间结果