Abstract / Summary

Count how many numbers up to n have digits that add up to an even number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 71% (100k+ submissions).

Typical patterns to solve this problem:

• Math
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The Solution.countEven method returns the count of integers in the range [1, num] whose digit-sum is even. It iterates once over the interval, maintaining a running parity flag that indicates whether the current number has an even digit-sum. The final result aggregates the flag values, yielding the total count.

Key Steps

The algorithm begins by initializing two accumulators.

result = 0
even = 1          # 1 represents True (even digit-sum), 0 represents False

A single for loop walks through every integer from 1 up to and including num.

for i in range(1, num + 1):

Inside the loop the parity of the digit-sum is updated. When the least-significant digit of i is non-zero, the parity flips with a bitwise XOR, because adding a non-zero digit changes the sum’s parity.

if i % 10 > 0:
    even ^= 1

If the current number ends with a zero, the simple toggle no longer holds; the digit-sum must be recomputed from scratch. The code extracts each digit with a while loop, accumulates the sum, and then derives the new parity by masking the least-significant bit and inverting it.

else:
    digitsum = 0
    x = i
    while x > 0:
        digitsum += x % 10
        x //= 10
    even = (digitsum & 1) ^ 1

After the parity for the current i is known, it is added to the running total. Because even is 1 for an even digit-sum and 0 otherwise, the addition directly contributes to the count.

result += even

When the loop finishes, result holds the desired count and is returned.

return result

Edge Cases Handled

When i ends with a zero, the simple parity toggle would be incorrect because the contribution of the trailing zero does not affect the digit-sum. The explicit recomputation in the else branch correctly resets the parity based on the full digit-sum, ensuring numbers like 10, 20, or 100 are evaluated accurately.

If num is zero, the for range produces no iterations; result remains at its initial value of 0, which correctly reflects that there are no positive integers to consider.

The while x > 0 loop gracefully handles any positive integer, including those with many digits, because integer division (//) reduces x until it reaches zero without overflow concerns.

Performance Optimizations

The primary optimization is the use of a parity flag (even) that is toggled with a single XOR operation for the majority of numbers. This avoids recomputing the digit-sum on every iteration, reducing the average work per loop step to constant time.

When a recomputation is necessary (numbers ending in zero), the algorithm employs bitwise operations to extract the parity of the digit-sum: (digitsum & 1) isolates the least-significant bit, and ^ 1 flips it to represent “even”. Bitwise manipulation is faster than arithmetic modulo operations.

The digit extraction loop uses integer division (//) and modulo (%) directly on the integer value, sidestepping any conversion to strings or lists, which would introduce additional overhead.

Overall, the method achieves a single pass over the input range with minimal per-iteration work, leveraging inexpensive bitwise operations and conditional recomputation only when required.

Imagine that every number has a special hidden weight made by adding up all its individual digits. When someone whispers a number, the goal is to count how many of the numbers leading up to that one have a weight that is even, just like a pair of matching socks.

The code starts by keeping a running tally of these special numbers. It walks through every number one by one starting from the very beginning. For most steps, it just keeps track of whether the weight flips from even to odd or back again. It is a bit like toggling a light switch on and off as it moves forward.

When it hits a number that ends in a zero, like ten or twenty, it stops to do some extra math. It takes that number apart digit by digit and adds them all up to see if that total sum is an even number. Once it checks the total, it updates its tally to include the new number if it fits the rule. It does this over and over until it reaches the final number asked for at the start. After all that counting, the total number of even candidates is found.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	Go			TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem						Ruby
	fsq	C++
	halfrost					Go
	JoshCrozier			JS
	lkwq007		Python
	muhammadfarhankt					Go
	suxrobGM							C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
trung-hn	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality