Given two integers num and k, consider a set of positive integers with the following properties:
k.num.Return the minimum possible size of such a set, or -1 if no such set exists.
Note:
0.Example 1:
Input: num = 58, k = 9 Output: 2 Explanation: 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 Explanation: 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 Explanation: The sum of an empty set is considered 0.
Constraints:
0 <= num <= 30000 <= k <= 9In #2310 Sum of Numbers With Units Digit K, the goal is to determine the minimum number of integers that end with digit k whose sum equals num. Every valid number can be written as 10 * x + k, meaning the units digit constraint only affects the remainder when summing values.
A practical strategy is to enumerate the number of elements used. If we pick i numbers ending with k, their combined units contribution is i * k. For the total to equal num, the remaining portion must be divisible by 10. Therefore, we check whether num - i * k is non‑negative and divisible by 10. Since units digits repeat every 10 multiples, we only need to test a small range of possible counts.
This observation turns the problem into a small enumeration with modular arithmetic, avoiding expensive dynamic programming. The approach efficiently determines the smallest valid count or concludes that no such combination exists.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumeration with modular arithmetic | O(1) | O(1) |
| Dynamic Programming (conceptual alternative) | O(num) | O(num) |
ThinkCode
Use these hints if you're stuck. Try solving on your own first.
Try solving this recursively.
Create a method that takes an integer x as a parameter. This method returns the minimum possible size of a set where each number has units digit k and the sum of the numbers in the set is x.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like this are common in technical interviews because they test mathematical insight and optimization thinking. While the exact question may vary, similar modular arithmetic and greedy reasoning problems appear in interviews at top tech companies.
Enumeration works because the units digit pattern repeats every 10 multiples. By checking a limited range of counts, we can determine whether the units digit condition and divisibility requirement can satisfy the target sum.
No specialized data structure is required for the optimal solution. The problem mainly relies on arithmetic reasoning and modular checks, so a few variables and a simple loop are sufficient.
The optimal approach uses enumeration with modular arithmetic. By trying small counts of numbers and checking whether num - i * k is divisible by 10, we can quickly determine if a valid combination exists. Since units digits cycle every 10 steps, only a small constant number of checks are required.