🔗 🟢 3099. Harshad Number 1101

tags: `Weekly Contest 391` `數學(Math)`

題意

如果一個整數能夠被其各位數字之和整除，則稱之為 哈沙德數(Harshad number) 。

給定一個整數 $x$ 。如果 $x$ 是 哈沙德數(Harshad number) ，則返回 $x$ 各位數字之和，否則返回 $-1$ 。

約束條件

$1 \leq x \leq 100$

思路：數學(Math)

令 $s$ 為 $x$ 各位數字之和， $tmp$ 為 $x$ 的備份。

根據題意，首先需要計算整數 $x$ 各位數字的和 $s$ ，這可以通過反覆對 $tmp$ 取模 $10$ 並累加得到。

然後檢查 $x$ 是否能夠被 $s$ 整除。如果是，則返回 $s$ ，否則返回 $-1$ 。

複雜度分析

時間複雜度： $\mathcal{O}(\log_{10}x)$ ，總共需要對 $x$ 取模 $log_{10}x$ 次。
空間複雜度： $\mathcal{O}(1)$ ，只需要常數空間。

class Solution:
    def sumOfTheDigitsOfHarshadNumber(self, x: int) -> int:
        s, tmp = 0, x
        while tmp:
            tmp, r = divmod(tmp, 10)
            s += r
        return s if x % s == 0 else -1

class Solution {
public:
    int sumOfTheDigitsOfHarshadNumber(int x) {
        int s = 0, tmp = x;
        while (tmp) {
            s += tmp % 10;
            tmp /= 10;
        }
        return x % s == 0? s : -1;
    }
};