Count Integers With Even Digit Sum

Difficulty: Easy | Acceptance: 70.10% | Paid: No Topics: Math, Simulation

Given a positive integer num, return the number of positive integers less than or equal to num whose digit sums are even.

The digit sum of an integer is the sum of all its digits.

Examples
Constraints
Approach 1: Simulation (String Conversion)
Approach 2: Simulation (Mathematical)

Examples

Example 1:

Input: num = 4
Output: 2
Explanation:
The integers are 1, 2, 3, 4.
Their digit sums are 1, 2, 3, 4.
Only 2 and 4 have even digit sums.

Example 2:

Input: num = 30
Output: 14
Explanation:
The integers with even digit sums are 2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, 28.
There are 14 integers in total.

Constraints

1 <= num <= 1000

Approach 1: Simulation (String Conversion)

Intuition We can iterate through every number from 1 to num. For each number, we convert it into a string to easily iterate over its digits, sum them up, and check if the sum is even.

Steps

Initialize a counter to 0.
Loop from 1 to num (inclusive).
Convert the current number to a string.
Iterate through each character in the string, convert it back to an integer, and add it to a running sum.
If the sum is divisible by 2, increment the counter.
Return the counter.

python

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

Complexity

Time: O(N * log N) where N is num. Since num is at most 1000, this is effectively linear. The log factor comes from the number of digits.
Space: O(log N) for the string representation of the number.
Notes: This approach is very readable but incurs the overhead of string allocation.

Approach 2: Simulation (Mathematical)

Intuition Instead of converting the number to a string, we can extract digits mathematically using the modulo operator (%) and integer division (/). This avoids the memory overhead of creating string objects.

Steps

Initialize a counter to 0.
Loop from 1 to num (inclusive).
For each number, initialize a sum variable to 0.
Use a while loop to extract the last digit using x % 10, add it to the sum, and remove the last digit using x /= 10 (or x //= 10 in Python).
If the final sum is divisible by 2, increment the counter.
Return the counter.

python

class Solution:\n    def countEven(self, num: int) -> int:\n        count = 0\n        for i in range(1, num + 1):\n            s = 0\n            x = i\n            while x:\n                s += x % 10\n                x //= 10\n            if s % 2 == 0:\n                count += 1\n        return count

Complexity

Time: O(N * log N) where N is num. The inner loop runs for the number of digits in i.
Space: O(1) as we only use a few integer variables for calculation.
Notes: This is generally more performant than the string conversion approach as it avoids heap allocations.