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 <= 9Problem Overview: You are given two integers num and k. The task is to find the minimum number of positive integers whose units digit equals k such that their total sum equals num. Each chosen number must end with digit k (for example: 7, 17, 27 if k = 7). If no such combination exists, return -1.
The key observation is that numbers with the same units digit behave predictably under addition. Only the last digit of the sum matters for feasibility. This turns the problem into a small search over possible counts instead of constructing the actual numbers.
Approach 1: Greedy Enumeration (O(1) time, O(1) space)
This approach relies on the repeating pattern of last digits when adding numbers that end with k. If you pick i numbers each ending with digit k, their combined units digit becomes (i * k) % 10. For the sum to equal num, the last digit must match num % 10. Because last digits repeat every 10 multiples, you only need to test values of i from 1 to 10.
For each candidate count i, check two conditions: the units digit requirement (i * k) % 10 == num % 10, and whether the total sum can reach num (i.e., i * k <= num). The second condition ensures the remaining value can be filled by adding tens to the chosen numbers, such as converting k into k + 10, k + 20, and so on. The first valid i is the minimum count. This method is effectively a constant-time greedy check combined with small enumeration.
Approach 2: Modular Arithmetic Optimization (O(1) time, O(1) space)
This version focuses directly on the modular equation governing the problem. If i numbers end with digit k, the final digit of the sum must satisfy (i * k) mod 10 = num mod 10. Instead of thinking about building numbers, you solve this as a modular arithmetic constraint. The smallest i that satisfies the equation and keeps i * k ≤ num gives the answer.
Because the modulus is 10, the search space is bounded to at most 10 candidates. This guarantees constant-time performance regardless of input size. The reasoning heavily uses properties from math and modular cycles, which is why this problem is categorized under mathematical reasoning rather than typical dynamic programming despite the combinational appearance.
Recommended for interviews: Interviewers expect the greedy enumeration or modular arithmetic insight. Brute-force construction of numbers shows understanding but wastes time. Recognizing that only the last digit matters reduces the problem to checking at most ten possibilities, which demonstrates strong number-pattern recognition and mathematical reasoning.
In this approach, we attempt to find the minimum number of integers with unit digit k such that their sum equals num. Start by considering the maximum number with unit's digit k that can fit into num and proceed backward, diminishing the count only when absolutely necessary.
In this Python solution, the problem is approached by considering the number of integers with unit k that can sum up to num. It starts from the maximum potential solution and backtracks checking if a solution is feasible for smaller sizes. The process iterates through possible numbers and evaluates if the residual can be zero.
Time Complexity: O(num/k) in the worst case scenario.
Space Complexity: O(1).
This approach leverages modular arithmetic by quickly checking conditions that ensure k-mod is consistent with achievable sums. Special cases are addressed directly, such as where k=0 but num is non-zero which is catchable by observing the remainder when dividing num by 10.
Here, we explore candidates under defined conditions until an effectual answer is determined. Iterating integers with incremental minimal inspection is central before uncovering a defined solution.
Time Complexity: O(10).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(num/k) in the worst case scenario. |
| Modular Arithmetic Optimization | Time Complexity: O(10). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Enumeration | O(1) | O(1) | Best general solution. Quickly test counts from 1–10 based on units digit behavior. |
| Modular Arithmetic Optimization | O(1) | O(1) | When reasoning mathematically about the equation (i * k) mod 10 = num mod 10. |
Leetcode 2310 Sum of Numbers With Units Digit K • ThinkCode • 2,318 views views
Watch 9 more video solutions →Practice Sum of Numbers With Units Digit K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor