Count Integers With Even Digit Sum

EASY

Description

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

Checkout 2 different approaches to solve Count Integers With Even Digit Sum. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 = 1 to num.
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.
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 of evenDigitSumCount is 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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Integers With Even Digit Sum. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Count Integers With Even Digit Sum

Patterns:

Math

Companies:

MindTree |