Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2310.html
2310. Sum of Numbers With Units Digit K
- Difficulty: Medium.
- Related Topics: Math, Dynamic Programming, Greedy, Enumeration.
- Similar Questions: Digit Count in Range, Count Integers With Even Digit Sum.
Problem
Given two integers num
and k
, consider a set of positive integers with the following properties:
-
The units digit of each integer is
k
. -
The sum of the integers is
num
.
Return the **minimum possible size of such a set, or -1
if no such set exists.**
Note:
-
The set can contain multiple instances of the same integer, and the sum of an empty set is considered
0
. -
The units digit of a number is the rightmost digit of the number.
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 <= 3000
-
0 <= k <= 9
Solution (Java, C++, Python)
-
class Solution { public int minimumNumbers(int nums, int k) { // Base Case Check if (nums == 0) { return 0; } int x = nums % 10; for (int i = 1; i <= 10; i++) { // check if the unit digits are equal for any case and if n>k*i if ((k * i) % 10 == x && nums >= k * i) { return i; } } // in case nothing matches return -1; } }
-
Todo
-
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 ############ # 2310. Sum of Numbers With Units Digit K # https://leetcode.com/problems/sum-of-numbers-with-units-digit-k/ class Solution: def minimumNumbers(self, num: int, k: int) -> int: if num == 0: return 0 A = [] INF = 100000 for x in range(k, num + 10, 10): A.append(x) A.reverse() @cache def go(index, total): if index >= len(A): return INF if total > num: return INF if total == num: return 0 # skip current res = go(index + 1, total) # take current if A[index] > 0: res = min(res, 1 + go(index, total + A[index])) return res ans = go(0, 0) if ans == 100000: return -1 return ans
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).