Count Integers With Even Digit Sum
EasyPrompt
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 <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We iterate through each integer from 1 up to num. For each integer, we calculate the sum of its digits. If the sum is even, we increment a counter. Finally, we return the total count.
Algorithm
- Initialize a counter variable
countto 0. - Loop through each integer
ifrom 1 tonum. - For each
i, create a helper function or an inner loop to calculate the sum of its digits.- To calculate the digit sum of a number
n:- Initialize
sum = 0. - While
n > 0:- Add the last digit (
n % 10) tosum. - Remove the last digit by integer division (
n = n / 10).
- Add the last digit (
- The final
sumis the digit sum.
- Initialize
- To calculate the digit sum of a number
- Check if the calculated digit sum is even (
sum % 2 == 0). - If the sum is even, increment the
countvariable. - After the loop completes, return the final
count.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. It involves checking every single number from 1 up to the given num.
Here's the breakdown:
- We start with a counter, say
evenDigitSumCount, initialized to zero. - We then loop from
i = 1tonum. - In each iteration, we take the current number
iand find the sum of its digits. This is done by repeatedly taking the number modulo 10 to get the last digit and then dividing the number by 10 to process the next digit, until the number becomes 0. - Once we have the digit sum, we check if it's an even number using the modulo operator (
digitSum % 2 == 0). - If the sum is even, we increment our
evenDigitSumCount. - After the loop has checked all numbers up to
num, the value ofevenDigitSumCountis our answer.
class Solution { public int countEven(int num) { int count = 0; for (int i = 1; i <= num; i++) { if (isDigitSumEven(i)) { count++; } } return count; } private boolean isDigitSumEven(int n) { int sum = 0; int temp = n; while (temp > 0) { sum += temp % 10; temp /= 10; } return sum % 2 == 0; }}Complexity
Time
O(N * log N) - We iterate `N` times (where `N` is `num`). In each iteration, we calculate the digit sum. For a number `i`, calculating its digit sum takes `O(log10(i))` time, as the number of digits is proportional to `log(i)`. Therefore, the total time complexity is the sum of `log(i)` for `i` from 1 to `N`, which is bounded by `O(N * log N)`.
Space
O(1) - We only use a few variables to store the count and intermediate sums, which is constant extra space regardless of the input `num`.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct as it follows the problem definition exactly.
Sufficiently fast for the given constraints (
num <= 1000).
Cons
Less efficient than the mathematical approach.
For a much larger
num, this approach would be too slow and could lead to a 'Time Limit Exceeded' error.
A more efficient approach relies on a mathematical observation. The number of positive integers up to num with an even digit sum is almost exactly half of num. The final count depends on the parity of the digit sum of num itself. If the digit sum of num is even, the count is num / 2. If the digit sum of num is odd, the count is (num - 1) / 2. This avoids iterating through all numbers and only requires a single digit sum calculation.
Algorithm
- Calculate the sum of the digits of the input number
num. Let's call itdigitSum. - To do this, repeatedly take the number modulo 10 and add it to a sum variable, then divide the number by 10, until it becomes 0.
- Check the parity of
digitSum. - If
digitSumis even (digitSum % 2 == 0), the answer isnum / 2. - If
digitSumis odd (digitSum % 2 != 0), the answer is(num - 1) / 2.
Walkthrough
Instead of checking every number, we can find a direct mathematical formula. The key insight is that the count of numbers with an even digit sum up to num is very close to num / 2.
Let's analyze the relationship. For almost every pair of consecutive numbers (x, x+1), their digit sums have different parities. For example, S(12)=3 (odd) and S(13)=4 (even). This means each such pair contributes exactly one number with an even digit sum. This pattern holds true unless x ends in a 9.
Through careful observation or induction, a simple rule emerges:
- Calculate the digit sum of
num. - If the digit sum of
numis even, it turns out that exactly half of the numbers from 1 tonumhave an even digit sum. The count isnum / 2. - If the digit sum of
numis odd, the count is(num - 1) / 2. This is becausenumitself has an odd digit sum and doesn't contribute to the count, and up tonum-1, the count of even-sum numbers is(num-1)/2.
This simplifies the problem to a single calculation.
class Solution { public int countEven(int num) { int digitSum = 0; int temp = num; while (temp > 0) { digitSum += temp % 10; temp /= 10; } if (digitSum % 2 == 0) { return num / 2; } else { // This is equivalent to (num - 1) / 2 for both even and odd num return num / 2; } }}Correction on the code snippet logic: The logic (num-1)/2 is correct. A simpler way to write the return statement is return (num - (digitSum % 2)) / 2;, but the if-else is clearer. The provided snippet has a slight error in the else block, it should be (num-1)/2. Here is the corrected version:
class Solution { public int countEven(int num) { int digitSum = 0; int temp = num; while (temp > 0) { digitSum += temp % 10; temp /= 10; } if (digitSum % 2 == 0) { return num / 2; } else { return (num - 1) / 2; } }}Complexity
Time
O(log N) - The time complexity is dominated by the calculation of the digit sum of `num`. The number of digits in `num` is proportional to `log10(num)`. This is significantly faster than the brute-force approach.
Space
O(1) - Only a few variables are used for the calculation, requiring constant extra space.
Trade-offs
Pros
Extremely efficient, with a constant number of operations relative to
num.Simple to implement once the pattern is understood.
Cons
The underlying mathematical pattern is not immediately obvious and requires some analysis or observation to discover.
Solutions
Solution
class Solution {public int countEven(int num) { int ans = 0; for (int i = 1; i <= num; ++i) { int s = 0; for (int x = i; x > 0; x /= 10) { s += x % 10; } if (s % 2 == 0) { ++ans; } } return ans; }}class Solution : def countEven ( self , num : int ) -> int : ans = 0 for x in range ( 1 , num + 1 ): s = 0 while x : s += x % 10 x //= 10 ans += s % 2 == 0 return ansclass Solution { public: int countEven ( int num ) { int ans = 0 ; for ( int i = 1 ; i <= num ; ++ i ) { int s = 0 ; for ( int x = i ; x ; x /= 10 ) { s += x % 10 ; } ans += s % 2 == 0 ; } return ans ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.