Abstract / Summary

Find the sum of all numbers up to n that end with digit k.

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 28% (100k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Enumeration
• Greedy
• Math

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 provided Solution class implements a method minimumNumbers that determines the smallest count of non-negative integers, each ending with the digit k, whose sum equals the target num. If such a combination cannot be formed, the method returns -1. The algorithm proceeds through a series of early checks, then builds reachable sums incrementally using a set-based breadth-first search.

Early Return Conditions

The first conditional block handles trivial inputs.

if num == 0:
    return 0

When the target sum is zero, no numbers are required, and the method returns immediately.

The next check captures the case where a single number suffices.

if num % 10 == k:
    return 1

If the last digit of num matches k, the number num itself ends with k and satisfies the requirement, so the answer is one.

The final early exit deals with an impossible scenario when k is zero but the target is not a multiple of ten.

if k == 0:
    return -1

Since every allowed number must end with 0, any sum that is not a multiple of ten cannot be constructed, and the method returns -1 without further work.

Incremental Construction of Reachable Sums

After the early exits, the algorithm initializes a set containing the sum 0, representing the starting point of the search.

have = set([0])

The outer loop iterates over a step counter, representing the number of elements used so far. The loop runs at most num times, but typically terminates earlier when a solution is found or when no new sums can be generated.

for step in range(1, num + 1):
    next = set()
    ...
    have = next
    if not have:
        break

Within each step, a new set next collects sums that can be reached by adding one more allowed number to any sum already present in have. The inner loops generate candidate numbers i that end with digit k by stepping through the arithmetic progression k, k+10, k+20, … up to num.

for i in range(k, num + 1, 10):
    for h in have:
        if h + i == num:
            return step
        if h + i < num:
            next.add(h + i)

If adding i to an existing sum h yields exactly num, the current step value is the minimal count and is returned immediately. Otherwise, if the new sum is still less than num, it is stored in next for exploration in the subsequent iteration.

Edge Cases Handled

The method explicitly addresses three edge conditions:

• The target num equals zero, returning 0 without further processing.
• The target’s last digit matches k, allowing a single-element solution.
• The digit k equals zero, which makes any non-multiple-of-ten target impossible, leading to an immediate -1.

These checks prevent unnecessary computation for inputs that have obvious answers.

Performance Optimizations

The algorithm incorporates several techniques that reduce unnecessary work:

• Early termination - The moment a sum equal to num is discovered, the method returns, avoiding the exploration of deeper steps.
• Pruned candidate generation - By iterating i only over numbers that end with k (range(k, num + 1, 10)), the code skips all values that could never be part of a valid combination, shrinking the inner loop’s workload.
• Set-based deduplication - Using a set for have and next ensures each reachable sum is stored only once per step, preventing redundant processing of identical states.
• Break on exhaustion - If a step produces no new sums (if not have: break), the outer loop exits early, recognizing that further steps cannot yield a solution.

These measures keep the search space as small as possible given the combinatorial nature of the problem.

Imagine you have a big pile of building blocks and you want to see if you can make a target number by adding smaller numbers together. Every single number you use must end with the same special digit, which is called k.

First, the code checks if the target number is already zero, because zero is like having nothing at all. Then, it checks if the target number itself ends with that special digit. If it does, you only need one piece to finish the job.

If the special digit is zero, it might be impossible to get exactly to the number you want unless the number itself ends in zero. The code keeps track of all the different totals you can make by adding these pieces together one by one. It starts by looking at what you can make with one piece, then two, and keeps going up.

Inside the loop, the code looks for numbers that end in your special digit. It adds a piece to your current total and keeps the new result if it is smaller than the target. If the newest result perfectly matches the target, the search is finished.

If the code runs out of ways to add these numbers without reaching the target, it realizes that it is impossible to solve the puzzle, so it gives up and stops.

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

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Java	Python		C++		TS
	WalkCCC	Java	Python		C++
	leetcode.ca	Java	Python		C++	Go	TS
	Progiez	Java	Python		C++
github	charles-wangkai	Java
	fsq				C++
	JoshCrozier			JS
	lkwq007		Python
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	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