#2310

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Sum of Numbers With Units Digit K

Determine the minimum set of positive integers whose units digits match k and sum exactly to num using DP patterns.

math dynamic programming greedy enumeration

Problem Statement

Given two integers num and k, find the smallest number of positive integers such that each integer ends with the digit k and their sum equals num. If no such set exists, return -1. This problem emphasizes a state transition dynamic programming approach where each partial sum depends on previous smaller sums.

For example, num = 58 and k = 9 allows sets like [9,49] or [19,39] with sum 58. Constraints: 0 <= num <= 3000, 0 <= k <= 9. Consider zero as a valid sum for an empty set. The solution involves systematically checking integer combinations while minimizing set size.

Examples

Example 1

Input: num = 58, k = 9

Output: 2

One valid set is [9,49], as the sum is 58 and each integer has a units digit of 9. Another valid set is [19,39]. It can be shown that 2 is the minimum possible size of a valid set.

Example 2

Input: num = 37, k = 2

Output: -1

It is not possible to obtain a sum of 37 using only integers that have a units digit of 2.

Example 3

Input: num = 0, k = 7

Output: 0

The sum of an empty set is considered 0.

Constraints

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

Solution Approach

Dynamic Programming Table

Construct a DP table where dp[s] stores the minimum count of integers with units digit k summing to s. Update dp iteratively for each integer candidate ending with k, ensuring the smallest set is tracked.

Greedy and Enumeration Shortcut

For small values of num and k, we can try adding multiples of k while checking the remainder modulo 10. This can quickly identify minimal sets without full DP, but may fail for edge cases where larger combinations are needed.

Recursive State Transition

Define a recursive function taking remaining sum and current count. At each step, subtract a number ending with k and recurse. Memoization prevents recomputation. Base cases handle exact sum, overreach, or zero sum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(num/k) in greedy checks to O(num) in DP. Space complexity depends on memoization or DP table size, which is O(num). Recursive approaches may use stack space up to O(num/k).

What Interviewers Usually Probe

Candidate quickly identifies units digit pattern for recursion or DP.
Candidate evaluates minimal set size instead of arbitrary sums.
Candidate handles edge cases: zero sum and impossible sums correctly.

Common Pitfalls or Variants

Common pitfalls

Ignoring sums where multiple combinations yield smaller counts.
Failing to handle num = 0 as an empty set.
Misapplying greedy without checking all remainder possibilities, leading to wrong -1 results.

Follow-up variants

Find minimum set with digits ending in k summing to a target multiple of 10.
Allow negative integers with units digit k and sum to num.
Count all possible sets meeting the units digit condition instead of minimum size.

FAQ

What is the main pattern used in Sum of Numbers With Units Digit K?

The main pattern is state transition dynamic programming, where each sum depends on previous smaller sums ending with digit k.

Can we solve this problem using only greedy?

Greedy works for simple cases but may fail for combinations requiring multiple integers; DP or recursion ensures correctness.

How do we handle num = 0 in this problem?

An empty set is considered valid, so the minimum set size is 0 when num = 0.

What is the time complexity of the DP solution?

Time complexity is O(num) for DP table updates; recursive memoized solutions are similar but include stack overhead.

How does GhostInterview help optimize the solution?

GhostInterview guides identifying minimal sets, avoiding recomputation with memoization, and handling edge cases like impossible sums or empty sets.

terminal

Solution

Solution 1: Math + Enumeration

Each number that meets the splitting condition can be represented as $10x_i + k$. If there are $n$ such numbers, then $\textit{num} - n \times k$ must be a multiple of $10$.

1

2

3

4

5

6

7

8

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        for i in range(1, num + 1):
            if (t := num - k * i) >= 0 and t % 10 == 0:
                return i
        return -1

Solution 2

#### Python3

1

2

3

4

5

6

7

8

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        for i in range(1, num + 1):
            if (t := num - k * i) >= 0 and t % 10 == 0:
                return i
        return -1

Solution 3

#### Python3

1

2

3

4

5

6

7

8

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        for i in range(1, num + 1):
            if (t := num - k * i) >= 0 and t % 10 == 0:
                return i
        return -1

Continue Practicing

#2708 maximum strength of a group #2745 construct the longest new string #2844 minimum operations to make a special number