Count Integers With Even Digit Sum solution and explanation
9 more videos on this problem
2180. Count Integers With Even Digit Sum || LeetCode 2180 || LeetCode Weekly Contest 281Bro Coders · 5:30 · 1K views
Leetcode | 2180. Count Integers with Even Digit Sum | Easy | Java SolutionDeveloper Docs · 5:01 · 1K views
Count Integers With Even Digit Sum | Leetcode 2180 | Contest 281 | 2 Approaches TC O(1)/O(n) 🔥🔥Coding Decoded · 5:47 · 1K views
2180. Count Integers With Even Digit Sum (Leetcode Easy)Programming Live with Larry · 2:37 · 481 views
Count Integers With Even Digit Sum | Leetcode 2180 | Amazon Google Facebook interview questionSuper Lazy Coder · 5:29 · 420 views
Count Integers With Even Digit Sum || Leetcode Weekly 281 ContestCode with Newton · 9:55 · 318 views
Weekly Contest 281 || Count Integers With Even Digit Sum || LeetcodeCODE · 5:39 · 128 views
Leetcode 2180 Count Integers With Even Digit SumMath Geeks · 1:25 · 75 views
Count Integers With Even Digit Sum - LeetCode 2180 - Javaalgobest - Computer Science · 2:38 · 69 views
Count Integer with even digit sum | python solution leetcodeTony Stark · 0:15 · 68 views
The 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
Approach overview
Problem Overview: Given an integer num, count how many integers in the range [1, num] have an even sum of digits. For example, 12 has digit sum 1 + 2 = 3 (odd), while 24 has 2 + 4 = 6 (even). The task is simply to count how many numbers up to num satisfy this condition.
Approach 1: Brute-Force Iteration (O(n * d) time, O(1) space)
Iterate through every integer from 1 to num. For each number, compute its digit sum by repeatedly extracting digits using n % 10 and n / 10. Check whether the digit sum is even, and increment the result if it is. The digit extraction process takes O(d) time where d is the number of digits, so the full iteration costs O(n * d). This approach is straightforward and easy to implement, making it useful for validating logic or when num is small. It fits naturally under simulation style problems.
Approach 2: Mathematical Pattern Recognition (O(d) time, O(1) space)
The key observation is that digit-sum parity flips frequently as numbers increase. For most consecutive numbers, increasing by one toggles the parity of the digit sum. Because of this pattern, roughly half the numbers from 1 to num have an even digit sum. The exact count depends only on the digit sum of num. Compute the digit sum of num. If that sum is even, the answer is num / 2. If the sum is odd, the answer is (num - 1) / 2. This works because the parity distribution remains balanced except at the boundary defined by num. Only one digit-sum calculation is required, which takes O(d) time. This approach relies on simple math reasoning instead of iterating through every number.
Recommended for interviews: Start with the brute-force explanation to show you understand the problem and can simulate digit operations correctly. Then derive the parity observation and present the mathematical solution. Interviewers typically expect the optimized math approach because it reduces the work from scanning all numbers to a constant-time calculation based on digit-sum parity.
Approach 1: Brute-Force Iteration
Brute-Force Iteration
This approach involves iterating through all integers from 1 to num and calculating their digit sum. We count the numbers that have an even digit sum by incrementing a counter whenever the digit sum is found to be even.
def digit_sum(n):
return sum(int(digit) for digit in str(n))
def count_even_digit_sum(num):
count = 0
for i in range(1, num + 1):
if digit_sum(i) % 2 == 0:
count += 1
return count
num = 30
print(count_even_digit_sum(num))public class Main {
public static int digitSum(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
public static int countEvenDigitSum(int num) {
int count = 0;
for (int i = 1; i <= num; i++) {
if (digitSum(i) % 2 == 0) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int num = 30;
System.out.println(countEvenDigitSum(num));
}
}#include <iostream>
int digitSum(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int countEvenDigitSum(int num) {
int count = 0;
for (int i = 1; i <= num; ++i) {
if (digitSum(i) % 2 == 0) {
++count;
}
}
return count;
}
int main() {
int num = 30;
std::cout << countEvenDigitSum(num);
return 0;
}function digitSum(n) {
let sum = 0;
while (n > 0) {
sum += n % 10;
n = Math.floor(n / 10);
}
return sum;
}
function countEvenDigitSum(num) {
let count = 0;
for (let i = 1; i <= num; i++) {
if (digitSum(i) % 2 === 0) {
count++;
}
}
return count;
}
const num = 30;
console.log(countEvenDigitSum(num));#include <stdio.h>
int digitSum(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int countEvenDigitSum(int num) {
int count = 0;
for (int i = 1; i <= num; ++i) {
if (digitSum(i) % 2 == 0) {
++count;
}
}
return count;
}
int main() {
int num = 30;
printf("%d", countEvenDigitSum(num));
return 0;
}using System;
public class Solution {
public int DigitSum(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
public int CountEvenDigitSum(int num) {
int count = 0;
for (int i = 1; i <= num; i++) {
if (DigitSum(i) % 2 == 0) {
count++;
}
}
return count;
}
public static void Main(string[] args) {
int num = 30;
Solution sol = new Solution();
Console.WriteLine(sol.CountEvenDigitSum(num));
}
}This Python solution defines a digit_sum function using list comprehension to compute the sum of an integer's digits. The main logic checks each number's digit sum.
Time Complexity: O(N * D), where N is the number of integers and D is the number of digits in each integer.
Space Complexity: O(1).
Approach 2: Mathematical Pattern Recognition
Mathematical Pattern Recognition
In this approach, observe that the transition of a number by one unit changes the parity of its digit sum (from even to odd or vice versa) mostly due to the last digit transition. Based on this observation, we can alternate between counting or skipping numbers based on the parity of the digit sum.
def count_even_digit_sum(num):
count = 0
sum = 0
for i in range(1, num + 1):
parity = (sum + (-1 if i % 10 == 0 else 1)) % 2
if parity == 0:
count += 1
sum += -8 if i % 10 == 0 else 1
return count
num = 30
print(count_even_digit_sum(num))public class Main {
public static int countEvenDigitSum(int num) {
int count = 0;
int sum = 0;
for (int i = 1; i <= num; ++i) {
int parity = (sum + (i % 10 == 0 ? -1 : 1)) % 2;
if (parity == 0) {
count++;
}
sum += i % 10 == 0 ? -8 : 1;
}
return count;
}
public static void main(String[] args) {
int num = 30;
System.out.println(countEvenDigitSum(num));
}
}#include <iostream>
int countEvenDigitSum(int num) {
int count = 0;
int sum = 0;
for (int i = 1; i <= num; ++i) {
int parity = (sum + (i % 10 == 0 ? -1 : 1)) % 2;
if (parity == 0) {
++count;
}
sum += i % 10 == 0 ? -8 : 1; // Adjusting sum based on the last digit
}
return count;
}
int main() {
int num = 30;
std::cout << countEvenDigitSum(num) << std::endl;
return 0;
}function countEvenDigitSum(num) {
let count = 0;
let sum = 0;
for (let i = 1; i <= num; i++) {
let parity = (sum + (i % 10 === 0 ? -1 : 1)) % 2;
if (parity === 0) {
count++;
}
sum += i % 10 === 0 ? -8 : 1;
}
return count;
}
const num = 30;
console.log(countEvenDigitSum(num));#include <stdio.h>
int countEvenDigitSum(int num) {
int count = 0;
for (int i = 1, sum = 0; i <= num; ++i) {
int parity = (sum + (i%10==0 ? -1 : 1)) % 2;
if (parity == 0) {
count++;
}
sum += i % 10 == 0 ? -8 : 1; // Adjusting considering end of digits
}
return count;
}
int main() {
int num = 30;
printf("%d", countEvenDigitSum(num));
return 0;
}using System;
public class Solution {
public int CountEvenDigitSum(int num) {
int count = 0;
int sum = 0;
for (int i = 1; i <= num; ++i) {
int parity = (sum + (i % 10 == 0 ? -1 : 1)) % 2;
if (parity == 0) {
count++;
}
sum += i % 10 == 0 ? -8 : 1;
}
return count;
}
public static void Main(string[] args) {
int num = 30;
Solution sol = new Solution();
Console.WriteLine(sol.CountEvenDigitSum(num));
}
}This Python solution identifies parity shifts by adjusting for zero transitions at each incremental digit, minimizing computational overhead.
Time Complexity: O(N)
Space Complexity: O(1)
Approach 3: Default Approach
function countEven(num: number): number {
let ans = 0;
for (let i = 1; i <= num; ++i) {
let s = 0;
for (let x = i; x; x = Math.floor(x / 10)) {
s += x % 10;
}
if (s % 2 == 0) {
++ans;
}
}
return ans;
}func countEven(num int) (ans int) {
for i := 1; i <= num; i++ {
s := 0
for x := i; x > 0; x /= 10 {
s += x % 10
}
if s%2 == 0 {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute-Force Iteration | Time Complexity: O(N * D), where N is the number of integers and D is the number of digits in each integer. |
| Mathematical Pattern Recognition | Time Complexity: O(N) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-Force Iteration | O(n * d) | O(1) | Simple implementation or when validating logic for small inputs |
| Mathematical Pattern Recognition | O(d) | O(1) | Optimal solution when recognizing digit-sum parity patterns |
Frequently asked questions
Is Count Integers With Even Digit Sum easy or hard?
Count Integers With Even Digit Sum is classified as an Easy problem on LeetCode. The brute-force solution is straightforward, while the optimal solution requires recognizing a simple mathematical parity pattern.
Count Integers With Even Digit Sum Python/Java solution
Python and Java implementations usually follow either a brute-force loop that calculates digit sums or the optimized math formula. The optimized version computes the digit sum of num and returns num / 2 if it is even, otherwise (num - 1) / 2.
How to solve Count Integers With Even Digit Sum in O(n)?
Iterate from 1 to num and compute the digit sum of each number using repeated modulo and division operations. If the sum is even, increment a counter. This simulation-based method runs in O(n * d) time where d is the number of digits in each number.
What is the best approach for Count Integers With Even Digit Sum?
The mathematical pattern approach is the best solution. Instead of checking every number, compute the digit sum of num and use the parity rule: if the digit sum is even, the result is num / 2; otherwise it is (num - 1) / 2. This runs in O(d) time where d is the number of digits.
Is Count Integers With Even Digit Sum asked at Google/Amazon/Meta?
Problems involving digit manipulation and mathematical patterns appear frequently in coding interviews at companies like Google, Amazon, and Meta. While this exact problem is categorized as easy, the reasoning pattern shows up in more complex math and digit DP questions.
What data structure is used in Count Integers With Even Digit Sum?
No specialized data structure is required. The problem mainly uses arithmetic operations on integers and simple iteration. The optimized solution relies on mathematical reasoning rather than additional storage.
What is the time complexity of Count Integers With Even Digit Sum?
The brute-force method takes O(n * d) time because each number from 1 to n requires computing its digit sum. The optimized mathematical solution only calculates the digit sum of n once, giving O(d) time and O(1) space.