# Count Integers With Even Digit Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-integers-with-even-digit-sum)
Canonical: https://scaleengineer.com/dsa/problems/count-integers-with-even-digit-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [MindTree](https://scaleengineer.com/companies/mindtree)
---
## Problem
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
## Brute Force Iteration
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.
**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`.
**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.
### Explanation
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:
1.  We start with a counter, say `evenDigitSumCount`, initialized to zero.
2.  We then loop from `i = 1` to `num`.
3.  In each iteration, we take the current number `i` and 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.
4.  Once we have the digit sum, we check if it's an even number using the modulo operator (`digitSum % 2 == 0`).
5.  If the sum is even, we increment our `evenDigitSumCount`.
6.  After the loop has checked all numbers up to `num`, the value of `evenDigitSumCount` is our answer.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter variable `count` to 0.
- Loop through each integer `i` from 1 to `num`.
- 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`) to `sum`.
      - Remove the last digit by integer division (`n = n / 10`).
    - The final `sum` is the digit sum.
- Check if the calculated digit sum is even (`sum % 2 == 0`).
- If the sum is even, increment the `count` variable.
- After the loop completes, return the final `count`.

## O(log N) Mathematical Solution
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.
**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.
**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.
### Explanation
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:
1.  Calculate the digit sum of `num`.
2.  If the digit sum of `num` is even, it turns out that exactly half of the numbers from 1 to `num` have an even digit sum. The count is `num / 2`.
3.  If the digit sum of `num` is odd, the count is `(num - 1) / 2`. This is because `num` itself has an odd digit sum and doesn't contribute to the count, and up to `num-1`, the count of even-sum numbers is `(num-1)/2`.

This simplifies the problem to a single calculation.

```java
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:
```java
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;
        }
    }
}
```
### Algorithm
- Calculate the sum of the digits of the input number `num`. Let's call it `digitSum`.
- 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 `digitSum` is even (`digitSum % 2 == 0`), the answer is `num / 2`.
- If `digitSum` is odd (`digitSum % 2 != 0`), the answer is `(num - 1) / 2`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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 ans
```

### CPP

```cpp
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 ; x /= 10 ) { s += x % 10 ; } ans += s % 2 == 0 ; } return ans ; } };
```