Count Integers With Even Digit Sum — Problem & Solution
Count Integers With Even Digit Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Integers With Even Digit Sum is an easy coding problem on math and simulation, asked in Amazon, TCS and Mindtree interviews.
- Difficulty: Easy
- Topics: Math, Simulation
- Asked at: Amazon, TCS, Mindtree
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a positive integer num, return the count of integers in the range [1, num] whose digit sum is even.
Example 1
Input: num = 4
Output: 2
Explanation: 2 and 4 have even digit sums; 1 and 3 do not.
Example 2
Input: num = 30
Output: 14
Explanation: The qualifying numbers are 2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26 and 28.
Example 3
Input: num = 1
Output: 0
Constraints
1 <= num <= 1000
Hints for Count Integers With Even Digit Sum
Hint 1
At
num <= 1000a direct loop over the range is plenty fast.Hint 2
Compute each number's digit sum by repeated
% 10and/ 10.Hint 3
Count the ones whose sum is even.
How to solve Count Integers With Even Digit Sum
The range is small, so the honest simulation is the right answer: compute each digit sum and count the even ones.
Approach
- Loop
ifrom 1 tonum. - Extract
i's digits with repeated modulo and division, summing as you go. - Increment the counter when the sum is even.
Why it works
Every integer in the range is examined exactly once and its digit sum computed exactly, so the count is exact by construction.
Complexity
- Time —
O(num · log num) - Space —
O(1)
Pitfalls
- Starting the loop at 0 counts an extra number — 0 has digit sum 0, which is even.
- A closed form exists (roughly
num / 2, adjusted at the boundary), but it is easy to get wrong; the loop is safer at these limits.
Reference solution
Python
def countEven(num: int) -> int:
count = 0
for i in range(1, num + 1):
s = 0
x = i
while x > 0:
s += x % 10
x //= 10
if s % 2 == 0:
count += 1
return countJava
public static int countEven(int num) {
int count = 0;
for (int i = 1; i <= num; i++) {
int s = 0, x = i;
while (x > 0) { s += x % 10; x /= 10; }
if (s % 2 == 0) count++;
}
return count;
}C++
int countEven(int num) {
int count = 0;
for (int i = 1; i <= num; i++) {
int s = 0, x = i;
while (x > 0) { s += x % 10; x /= 10; }
if (s % 2 == 0) count++;
}
return count;
}JavaScript
var countEven = function(num) {
let count = 0;
for (let i = 1; i <= num; i++) {
let s = 0, x = i;
while (x > 0) { s += x % 10; x = Math.floor(x / 10); }
if (s % 2 === 0) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.