Skip to main content
Talentd

Count Integers With Even Digit Sum - Solution & Explanation

EasyMathSimulation12 min readAsked at: Mindtree
Practice this problem

Problem Statement

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.

This C solution defines a digitSum function to calculate sum of digits of a number. The main function iterates through each number from 1 to num and checks if the digit sum is even, counting it if so.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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) since only a few variables are used.

Try this approach in the editor ā†’

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.

This C solution uses a running sum and adjusts it based on the units digit to track the parity change. Observations about the patterns of carryovers in decimal numbers are crucial.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N)
Space Complexity: O(1)

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1) since only a few variables are used.

Mathematical Pattern Recognition

Time Complexity: O(N)
Space Complexity: O(1)

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute-Force IterationO(n * d)O(1)Simple implementation or when validating logic for small inputs
Mathematical Pattern RecognitionO(d)O(1)Optimal solution when recognizing digit-sum parity patterns

Video Solution

2180. Count Integers With Even Digit Sum || LeetCode 2180 || LeetCode Weekly Contest 281 ā€¢ Bro Coders ā€¢ 1,209 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

Practice Count Integers With Even Digit Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find if Digit Game Can Be Won

Next

Number of Ways to Buy Pens and Pencils