题目描述
给你一个正整数 num
,请你统计并返回 小于或等于 num
且各位数字之和为 偶数 的正整数的数目。
正整数的 各位数字之和 是其所有位上的对应数字相加的结果。
样例
输入:num = 4
输出:2
解释:
只有 2 和 4 满足小于等于 4 且各位数字之和为偶数。
输入:num = 30
输出:14
解释:
只有 14 个整数满足小于等于 30 且各位数字之和为偶数,分别是:
2、4、6、8、11、13、15、17、19、20、22、24、26 和 28。
限制
1 <= num <= 1000
算法
(模拟) $O(n \log n)$
- 直接暴力枚举每个数字并进行判断。
时间复杂度
- 判断的时间复杂度为 $O(\log n)$,故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
bool check(int x) {
int r = 0;
while (x) {
r += x % 10;
x /= 10;
}
return r % 2 == 0;
}
public:
int countEven(int num) {
int ans = 0;
for (int x = 1; x <= num; x++)
if (check(x))
ans++;
return ans;
}
};