##### 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).