Watch 10 video solutions for Count Integers With Even Digit Sum, a easy level problem involving Math, Simulation. This walkthrough by Bro Coders has 1,184 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 a positive integer is the sum of all its digits.
Example 1:
Input: num = 4 Output: 2 Explanation: The only integers less than or equal to 4 whose digit sums are even are 2 and 4.
Example 2:
Input: num = 30 Output: 14 Explanation: The 14 integers less than or equal to 30 whose digit sums are even are 2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.
Constraints:
1 <= num <= 1000Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-Force Iteration | O(n * d) | O(1) | Simple implementation or when validating logic for small inputs |
| Mathematical Pattern Recognition | O(d) | O(1) | Optimal solution when recognizing digit-sum parity patterns |