LeetCode 2310 - Sum of Numbers With Units Digit K

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Greedy, Enumeration

Solution

Problem Understanding

This problem asks us to construct a set of positive integers such that:

Every number in the set has a units digit equal to k.
The sum of all numbers equals num.
We want the smallest possible number of integers in the set.

If it is impossible to create such a set, we return -1.

An important detail is that numbers can repeat. This means we are not restricted to unique values. For example, if k = 5, we may use [5, 5, 15] or even [25, 25], as long as every number ends in 5 and their sum equals num.

The problem also explicitly states that the empty set has sum 0, which creates an important special case. If num = 0, we can immediately return 0, regardless of the value of k.

Restating the Problem

We need to determine the minimum number of integers ending in digit k whose sum equals num.

Instead of thinking about the entire value of each number, the key observation is that only the last digit matters. Since every number ends in k, the sum's units digit depends only on how many such numbers we choose.

For example:

If k = 9 and we choose two numbers, their last digits contribute 9 + 9 = 18, whose units digit is 8.
If num = 58, whose last digit is 8, then using two numbers is potentially valid.

The constraints are small:

0 <= num <= 3000
0 <= k <= 9

Although num is not very large, this problem is actually much simpler than a full dynamic programming or subset sum problem. The small range of possible units digits allows a mathematical observation to solve it efficiently.

Important Edge Cases

Several cases can easily trip up a naive implementation.

If num = 0, the answer is always 0 because the empty set is valid.

If k = 0, every chosen number must end in 0, meaning every number is divisible by 10. In this case, only sums divisible by 10 are possible.

If num < k, we cannot simply reject the answer. For example, num = 12 and k = 2 works because [12] is valid, even though num < 20. What matters is whether a valid combination of ending digits exists.

We must also handle cases where no solution exists, such as num = 37 and k = 2. No number of integers ending in 2 can produce a sum ending in 7.

Approaches

Brute Force Approach

A brute-force solution would try every possible count of numbers and determine whether some combination of integers ending in k can sum to num.

This can be modeled similarly to an unbounded knapsack or dynamic programming problem. We could generate all numbers ending in k up to num:

k, k + 10, k + 20, ...

Then attempt to find the minimum number of such values that sum to num.

For example, if num = 58 and k = 9, the candidates are:

9, 19, 29, 39, 49

We could use dynamic programming to compute the minimum count for every intermediate sum.

This works because it systematically explores all valid possibilities. However, it is unnecessarily expensive because the problem has a much stronger mathematical structure. We do not actually care about the exact numbers chosen, only their final digit contribution.

Key Insight for the Optimal Solution

The crucial observation is that only the units digit matters.

Suppose we choose x numbers. Since every number ends in k, the units digit of their sum is:

(x * k) % 10

For the sum to equal num, the units digit must match:

(x * k) % 10 == num % 10

We also must ensure the total sum does not exceed num:

x * k <= num

because each chosen number is at least k.

Since units digits repeat every 10 multiplications, we only need to test:

x = 1 to 10

If we find a valid x, it is automatically the minimum because we check in increasing order.

This turns the problem into a very small enumeration problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(num²)	O(num)	Dynamic programming over possible sums
Optimal	O(1)	O(1)	Try at most 10 possible counts

Algorithm Walkthrough

Handle the special case where num = 0.

If the target sum is zero, the empty set is valid, so return 0. 2. Try every possible number of elements from 1 to 10.

We only need to test ten possibilities because units digits repeat modulo 10. After ten multiplications, the pattern starts repeating. 3. Check whether the units digit matches.

For each candidate count count, compute:

(count * k) % 10

If this equals num % 10, then the last digit requirement is satisfied. 4. Check whether the total minimum sum is feasible.

Since each number must be positive and end in k, the smallest possible number we can choose is k itself. Therefore:

count * k <= num

must hold. 5. Return the first valid count.

Because we iterate from smallest to largest, the first valid count is guaranteed to be minimal. 6. Return -1 if no count works.

If none of the ten possibilities satisfy both conditions, then no valid set exists.

Why it works

The key invariant is that the units digit of a sum depends only on the units digits of its components. Since every chosen number ends in k, choosing x numbers always contributes a units digit of:

(x * k) % 10

The modulo cycle repeats every 10, so checking beyond 10 counts would only repeat previous patterns. The feasibility condition x * k <= num guarantees that the required total sum can actually be reached by increasing some numbers by multiples of 10. Therefore, the first valid x found is always the minimum answer.

Python Solution

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0

        for count in range(1, 11):
            if (count * k) % 10 == num % 10 and count * k <= num:
                return count

        return -1

Implementation Explanation

The first condition checks whether num is zero. Since the empty set is allowed and sums to zero, we immediately return 0.

Next, we iterate from 1 to 10, testing all possible set sizes. We only need ten iterations because modulo 10 arithmetic repeats.

For each candidate count, we verify two conditions.

The first condition:

(count * k) % 10 == num % 10

ensures that the units digit of the sum matches the units digit of num.

The second condition:

count * k <= num

ensures feasibility. Since the smallest number ending in k is k itself, the minimum achievable sum with count numbers is count * k.

As soon as both conditions are satisfied, we return count. Since we search in ascending order, this is guaranteed to be the minimum possible size.

If no valid count exists, we return -1.

Go Solution

func minimumNumbers(num int, k int) int {
	if num == 0 {
		return 0
	}

	for count := 1; count <= 10; count++ {
		if (count*k)%10 == num%10 && count*k <= num {
			return count
		}
	}

	return -1
}

Go-Specific Implementation Differences

The Go implementation follows the exact same logic as the Python version. Since the constraints are small, integer overflow is not a concern.

Unlike Python, Go uses an explicit for loop with integer variables:

for count := 1; count <= 10; count++

No additional data structures are required, so the implementation remains constant space.

Worked Examples

Example 1

num = 58, k = 9

We try counts from 1 to 10.

Count	count × k	Units Digit	Matches `58 % 10 = 8`?	Feasible?
1	9	9	No	Yes
2	18	8	Yes	Yes

At count = 2:

(2 × 9) % 10 = 8

and:

18 <= 58

So the answer is:

A valid construction is:

[9, 49]

Example 2

num = 37, k = 2

Count	count × k	Units Digit	Matches `37 % 10 = 7`?
1	2	2	No
2	4	4	No
3	6	6	No
4	8	8	No
5	10	0	No
6	12	2	No
7	14	4	No
8	16	6	No
9	18	8	No
10	20	0	No

No valid count produces units digit 7.

Result:

-1

Example 3

num = 0, k = 7

Since the target sum is zero, we immediately return:

The empty set is valid.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	At most 10 iterations are checked
Space	O(1)	Only a few variables are used

The runtime is constant because the loop always executes at most ten times, independent of num. The space complexity is also constant since no extra data structures are allocated.

Test Cases

solution = Solution()

assert solution.minimumNumbers(58, 9) == 2  # Example 1
assert solution.minimumNumbers(37, 2) == -1  # Example 2
assert solution.minimumNumbers(0, 7) == 0  # Example 3

assert solution.minimumNumbers(10, 0) == 1  # Single number ending in 0
assert solution.minimumNumbers(20, 0) == 1  # Exact match with one number
assert solution.minimumNumbers(11, 0) == -1  # Cannot form non-zero units digit

assert solution.minimumNumbers(12, 2) == 1  # Single number works
assert solution.minimumNumbers(5, 5) == 1  # Exact single element
assert solution.minimumNumbers(6, 7) == -1  # Impossible, minimum exceeds num

assert solution.minimumNumbers(18, 9) == 2  # Two 9-ending numbers
assert solution.minimumNumbers(24, 4) == 1  # Single number ending in 4
assert solution.minimumNumbers(17, 7) == 1  # Single number exact match

assert solution.minimumNumbers(3000, 9) >= 1  # Upper bound stress test
assert solution.minimumNumbers(1, 1) == 1  # Smallest non-zero valid case
assert solution.minimumNumbers(1, 2) == -1  # Smallest impossible case

Test	Why
`(58, 9)`	Validates standard case with minimum count > 1
`(37, 2)`	Validates impossible case
`(0, 7)`	Verifies empty set behavior
`(10, 0)`	Tests `k = 0` with exact match
`(11, 0)`	Tests impossible non-zero units digit with `k = 0`
`(12, 2)`	Verifies single-number solution
`(6, 7)`	Tests infeasible minimum sum
`(18, 9)`	Verifies multi-number solution
`(3000, 9)`	Stress test at upper constraint
`(1, 2)`	Small impossible input

Edge Cases

`num = 0`

This is the most important special case. Since the problem defines the empty set as having sum 0, the correct answer is always 0. A naive implementation might accidentally return -1 because it never considers using zero elements. The implementation handles this immediately with:

if num == 0:
    return 0

`k = 0`

When k = 0, every number must end in 0, meaning every chosen number is a multiple of 10. This means only sums ending in 0 are possible. For example:

num = 11, k = 0

cannot work because the units digit does not match. The modulo check naturally handles this case without any special logic.

Small `num` Compared to `k`

A common mistake is assuming that if num < k, the answer must be impossible. This is incorrect because valid numbers can be larger than k while still ending in k.

For example:

num = 12, k = 2

works because [12] is valid. The implementation correctly checks the units digit relationship rather than comparing only magnitudes.

No Valid Units Digit Combination

Some inputs are impossible because repeated additions of k never produce the required units digit.

For example:

num = 37, k = 2

produces repeating units digits:

2, 4, 6, 8, 0

and never reaches 7. The algorithm safely returns -1 after checking all ten possibilities.

LeetCode 2310 - Sum of Numbers With Units Digit K

Solution

Problem Understanding

Restating the Problem

Important Edge Cases

Approaches

Brute Force Approach

Key Insight for the Optimal Solution

Algorithm Walkthrough

Why it works

Python Solution

Implementation Explanation

Go Solution

Go-Specific Implementation Differences

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Edge Cases

num = 0

k = 0

Small num Compared to k

No Valid Units Digit Combination

`num = 0`

`k = 0`

Small `num` Compared to `k`