Count Integers With Even Digit Sum - Practice Coding Problems

Count Integers With Even Digit Sum - Problem

Math Simulation Easy

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.

Input & Output

Example 1 — Small Number

$ Input: num = 4

› Output: 2

💡 Note: Check numbers 1-4: 1(sum=1,odd), 2(sum=2,even), 3(sum=3,odd), 4(sum=4,even). Count of even sums = 2.

Example 2 — Larger Number

$ Input: num = 30

› Output: 14

💡 Note: Among numbers 1-30, exactly 14 have even digit sums (like 2,4,6,8,11,13,15,17,20,22,24,26,28,29).

Example 3 — Single Digit

$ Input: num = 9

› Output: 4

💡 Note: Numbers 1-9 with even digit sums: 2,4,6,8. Total count = 4.

Constraints

1 ≤ num ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Given positive integer num = 4

Process

Check each number 1 to 4, calculate digit sums

Output

Count numbers with even digit sums

Key Takeaway

🎯 Key Insight: Count numbers where the sum of digits is divisible by 2

Asked in

G Google 15 M Microsoft 12

The key insight is recognizing that digit sum parity follows mathematical patterns. The optimal approach iterates through all numbers calculating digit sums. Time: O(n × log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Number	O(n × log n)	O(1)	Iterate through all numbers from 1 to num and count those with even digit sums
Mathematical Pattern Recognition	O(log n)	O(1)	Recognize that approximately half of all numbers have even digit sums

Brute Force - Check Every Number — Algorithm Steps

Iterate from 1 to num
For each number, calculate digit sum by extracting digits
Count numbers with even digit sums

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Number

Go through numbers 1, 2, 3, 4...

Calculate Digit Sum

Add up all digits: 12 → 1+2=3

Count Even Sums

Increment counter if sum is even

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int digitSum(int n) {
    int total = 0;
    while (n > 0) {
        total += n % 10;
        n /= 10;
    }
    return total;
}

int solution(int num) {
    int count = 0;
    for (int i = 1; i <= num; i++) {
        if (digitSum(i) % 2 == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    int num;
    scanf("%d", &num);
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log n)

Iterate through n numbers, each taking O(log n) time to calculate digit sum

⚡ Linearithmic

Space Complexity

O(1)

Only using variables to track count and current number

✓ Linear Space

32.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler