Count Integers With Even Digit Sum - Solution & Explanation

Problem Overview: Given an integer num, count how many integers in the range [1, num] have an even sum of digits. For example, 12 has digit sum 1 + 2 = 3 (odd), while 24 has 2 + 4 = 6 (even). The task is simply to count how many numbers up to num satisfy this condition.

Approach 1: Brute-Force Iteration (O(n * d) time, O(1) space)

Iterate through every integer from 1 to num. For each number, compute its digit sum by repeatedly extracting digits using n % 10 and n / 10. Check whether the digit sum is even, and increment the result if it is. The digit extraction process takes O(d) time where d is the number of digits, so the full iteration costs O(n * d). This approach is straightforward and easy to implement, making it useful for validating logic or when num is small. It fits naturally under simulation style problems.

Approach 2: Mathematical Pattern Recognition (O(d) time, O(1) space)

The key observation is that digit-sum parity flips frequently as numbers increase. For most consecutive numbers, increasing by one toggles the parity of the digit sum. Because of this pattern, roughly half the numbers from 1 to num have an even digit sum. The exact count depends only on the digit sum of num. Compute the digit sum of num. If that sum is even, the answer is num / 2. If the sum is odd, the answer is (num - 1) / 2. This works because the parity distribution remains balanced except at the boundary defined by num. Only one digit-sum calculation is required, which takes O(d) time. This approach relies on simple math reasoning instead of iterating through every number.

Recommended for interviews: Start with the brute-force explanation to show you understand the problem and can simulate digit operations correctly. Then derive the parity observation and present the mathematical solution. Interviewers typically expect the optimized math approach because it reduces the work from scanning all numbers to a constant-time calculation based on digit-sum parity.