LeetCode 2180 - Count Integers With Even Digit Sum

LeetCode Problem 2180

Difficulty: 🟢 Easy
Topics: Math, Simulation

Solution

Problem Understanding

The problem asks us to count all positive integers less than or equal to a given number num such that the sum of their digits is even. In other words, we are asked to evaluate each integer 1 through num, compute the sum of its digits, and check whether that sum is divisible by 2. If it is, we include it in our count. The input is a single integer num, constrained between 1 and 1000, which is a relatively small range, meaning a straightforward approach can be feasible.

Key points include understanding that the digit sum of a number like 123 is 1 + 2 + 3 = 6, and since 6 is even, 123 would be counted. Edge cases that might cause errors include very small inputs like 1 or 2, and numbers near the upper limit 1000. The problem guarantees that the input is always positive and at most 1000, so we do not need to handle zero, negative numbers, or extremely large numbers.

Approaches

A brute-force approach is to iterate over every number from 1 to num, calculate its digit sum by converting it to a string or using arithmetic operations, and check if it is even. While this approach is correct and straightforward, it can be inefficient if num were much larger. However, given the constraints (num <= 1000), the brute-force method is acceptable.

The key insight for a more optimal approach is recognizing that we do not need to store any numbers or intermediate results. We simply iterate from 1 to num, calculate the digit sum in-place, and increment a counter if the sum is even. This eliminates unnecessary space usage and keeps the code simple.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * d)	O(1)	Iterate each number, sum its digits (d is digits in number), and check parity
Optimal	O(n * d)	O(1)	Same as brute-force here, but simplified; no extra data structures needed

Algorithm Walkthrough

1. Initialize a counter variable count to zero. This will store the total number of integers with even digit sums.
2. Iterate through all integers i from 1 to num inclusive.
3. For each i, calculate the sum of its digits. This can be done either by repeatedly taking i % 10 and dividing i by 10 until it becomes 0, or by converting the integer to a string and summing the integer value of each character.
4. Check if the calculated sum is divisible by 2. If it is, increment the count.
5. After finishing the loop, return the value of count.

Why it works: The algorithm guarantees correctness because it explicitly evaluates the digit sum of every integer in the given range, and only increments the count when the sum is even. Since all integers up to num are considered, no valid numbers are missed, and no invalid numbers are counted.

Python Solution

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

This implementation first initializes the count variable to zero. It then loops through all integers from 1 to num, computes the sum of digits using a generator expression, checks if the sum is even, and increments the count accordingly. Finally, it returns the count.

Go Solution

func countEven(num int) int {
    count := 0
    for i := 1; i <= num; i++ {
        n := i
        digitSum := 0
        for n > 0 {
            digitSum += n % 10
            n /= 10
        }
        if digitSum % 2 == 0 {
            count++
        }
    }
    return count
}

In Go, we use a standard for loop and arithmetic operations to calculate the digit sum. Unlike Python, we do not convert the number to a string. Instead, we repeatedly extract the last digit using modulo 10, add it to digitSum, and reduce the number by dividing by 10. This avoids unnecessary string allocation.

Worked Examples

Example 1: num = 4

i	digit sum	even?	count
1	1	no	0
2	2	yes	1
3	3	no	1
4	4	yes	2

Output: 2

Example 2: num = 30

i	digit sum	even?	count
1	1	no	0
2	2	yes	1
3	3	no	1
4	4	yes	2
5	5	no	2
...	...	...	...
30	3	no	14

Output: 14

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * d)	For each number from 1 to num, we sum its digits. d is the number of digits, at most 4 for num <= 1000.
Space	O(1)	Constant extra space is used; no dynamic data structures are needed.

Even though the loop iterates num times, the small size of num ensures efficiency. Space usage is minimal, making this approach both simple and effective.

Test Cases

# test cases
s = Solution()
assert s.countEven(4) == 2  # Basic small input
assert s.countEven(30) == 14  # Example from problem
assert s.countEven(1) == 0  # Edge case, smallest input
assert s.countEven(2) == 1  # Edge case, first even digit sum
assert s.countEven(1000) == 500  # Maximum input, should handle large numbers efficiently
assert s.countEven(11) == 5  # Odd and even numbers mixed
assert s.countEven(19) == 9  # Larger range with alternating sums

Test	Why
4	Simple case, small number
30	Standard example, mid-range
1	Lower boundary case
2	First even digit sum number
1000	Upper boundary, tests performance
11	Mix of numbers and sums
19	Validates alternating pattern correctness

Edge Cases

The first edge case is when num = 1. The only integer to check is 1, which has an odd digit sum, so the function must correctly return 0. The implementation handles this because the loop starts at 1 and only increments the count if the digit sum is even.

The second edge case is num = 2. Here, the number 2 has an even digit sum, and the function should return 1. The implementation correctly counts this scenario because it evaluates each number individually.

The third edge case is the upper bound num = 1000. The digit sum of 1000 is 1, which is odd, so it should not be counted. The function efficiently loops through all numbers up to 1000 and evaluates each without exceeding memory limits, correctly returning the total count of numbers with even digit sums.