题目描述
如果一个整数能够被其各个数位上的数字之和整除,则称之为 哈沙德数(Harshad number)。给你一个整数 x
。如果 x
是 哈沙德数,则返回 x
各个数位上的数字之和,否则,返回 -1
。
样例
输入: x = 18
输出: 9
解释:
x 各个数位上的数字之和为 9。18 能被 9 整除。因此 18 是哈沙德数,答案是 9。
输入: x = 23
输出: -1
解释:
x 各个数位上的数字之和为 5。23 不能被 5 整除。因此 23 不是哈沙德数,答案是 -1。
限制
1 <= x <= 100
算法
(模拟) $O(\log x)$
- 通过每次模 10 以及除以 10 的方式求出 $x$ 各位和。
时间复杂度
- 遍历每个数位一次,故时间复杂度为 $O(\log x)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int sumOfTheDigitsOfHarshadNumber(int x) {
int sum = 0, t = x;
while (t) {
sum += t % 10;
t /= 10;
}
return x % sum ? -1 : sum;
}
};