Easy

题目描述

给定一个正整数 num，返回小于或等于 num 且各位数字之和为偶数的正整数个数。

正整数的各位数字之和是其所有数字的和。

示例 1：

输入: num = 4
输出: 2
解释: 小于或等于 4 且各位数字之和为偶数的整数只有 2 和 4。

示例 2：

输入: num = 30
输出: 14
解释: 小于或等于 30 且各位数字之和为偶数的 14 个整数是：
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, 28。

约束条件：

  • 1 <= num <= 1000

提示：

  • 遍历从 1 到 num 的所有整数。
  • 对于任何整数，提取各个数字来计算它们的和，并检查是否为偶数。

解题思路

解题思路

这道题目要求统计从 1 到 num 范围内所有各位数字之和为偶数的正整数个数。

方法一：暴力模拟（推荐）

最直接的方法是遍历从 1 到 num 的所有整数，对每个数字计算其各位数字之和，判断是否为偶数。

具体步骤：

  1. 遍历从 1 到 num 的每个整数
  2. 对于每个整数，通过不断除以 10 来提取各位数字
  3. 计算所有数字的和
  4. 判断和是否为偶数，如果是则计数加一

方法二：数学规律

我们也可以观察到一个数学规律：在任意连续的正整数范围内，各位数字之和为偶数和奇数的数字个数基本相等。但由于题目约束较小（num <= 1000），暴力方法已经足够高效。

时间复杂度为 O(n × log n)，其中 n 为 num 的值，log n 为计算数字位数之和的时间。由于约束条件下 num 最大为 1000，这种方法完全可行。

代码实现

class Solution {
public:
    int countEven(int num) {
        int count = 0;
        for (int i = 1; i <= num; i++) {
            int sum = 0;
            int temp = i;
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }
            if (sum % 2 == 0) {
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def countEven(self, num: int) -> int:
        count = 0
        for i in range(1, num + 1):
            digit_sum = sum(int(digit) for digit in str(i))
            if digit_sum % 2 == 0:
                count += 1
        return count

public class Solution {
    public int CountEven(int num) {
        int count = 0;
        for (int i = 1; i <= num; i++) {
            int sum = 0;
            int temp = i;
            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }
            if (sum % 2 == 0) {
                count++;
            }
        }
        return count;
    }
}

var countEven = function(num) {
    let count = 0;
    for (let i = 1; i <= num; i++) {
        let digitSum = 0;
        let temp = i;
        while (temp > 0) {
            digitSum += temp % 10;
            temp = Math.floor(temp / 10);
        }
        if (digitSum % 2 === 0) {
            count++;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log n)需要遍历 1 到 num 的所有数字，每个数字需要 O(log n) 时间计算各位数字之和
空间复杂度O(1)只使用常数额外空间

相关题目