# Sum of Numbers With Units Digit K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-numbers-with-units-digit-k)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-numbers-with-units-digit-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## 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`

# Approaches
## Brute-force Recursion
This approach attempts to solve the problem by exploring all possible combinations of numbers that end in `k` to see if they can sum up to `num`. A recursive function is defined to try subtracting every possible valid number (e.g., `k`, `10+k`, `20+k`, etc.) from the target `num` and finding the minimum count of numbers used in this process.
**Time:** Exponential - O(c^N) where N is `num` and c is the number of choices at each step. The function branches for every possible number ending in `k`, leading to an exponential number of calls. · **Space:** O(num) - The maximum depth of the recursion stack can be proportional to `num` in the worst case (e.g., if `k=1` and we keep subtracting 11, 21, etc.).
**Pros:** Conceptually simple and a direct translation of the problem statement.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to use a recursive function, let's call it `solve(target)`, which calculates the minimum number of items to reach a `target` sum. The function works as follows:

1.  If the `target` is 0, it means we've found a valid combination, and the size of this sub-solution is 0. We return 0.
2.  If the `target` becomes negative, it means the last number we subtracted was too large, so this path is invalid. We return an indicator of failure, such as infinity.
3.  For a positive `target`, we iterate through all valid numbers `c` that we can use (positive integers ending in `k`). For each `c`, we recursively call `solve(target - c)`. We are looking for the minimum result among `1 + solve(target - c)` over all possible choices of `c`.

This method is a classic brute-force search. It explores the entire search space, but because it recalculates solutions for the same `target` values multiple times, its performance is very poor.
### Algorithm
*   Define a recursive function `solve(target)` that returns the minimum number of integers ending in `k` that sum to `target`.
*   **Base Case 1:** If `target == 0`, it means we have successfully formed the sum, so we need 0 more numbers. Return 0.
*   **Base Case 2:** If `target < 0`, it's an invalid path. Return a value indicating impossibility, like `Integer.MAX_VALUE`.
*   **Recursive Step:** Initialize a variable `minSize` to `Integer.MAX_VALUE`.
*   Iterate through all possible positive integers `c` that end with digit `k` and are less than or equal to the current `target` (e.g., `k`, `10+k`, `20+k`, ... or `10`, `20`, ... if `k=0`).
*   For each `c`, make a recursive call `solve(target - c)`.
*   If the recursive call does not return `Integer.MAX_VALUE`, it means a solution was found for the subproblem. Update `minSize = Math.min(minSize, 1 + solve(target - c))`.
*   Return `minSize`.
*   The initial call is `solve(num)`. If the result is `Integer.MAX_VALUE`, it means no solution exists, so return -1.

## Dynamic Programming
This approach improves upon the brute-force recursion by using dynamic programming to avoid recomputing results for the same subproblems. It's analogous to the classic Unbounded Knapsack or Change-making problem. We build a `dp` array from the bottom up, where `dp[i]` stores the minimum number of integers ending in `k` that sum up to `i`.
**Time:** O(num^2) - The outer loop runs `num` times, and the inner loop can run up to `num / 10` times in the worst case, leading to a quadratic time complexity. · **Space:** O(num) - We need an array of size `num + 1` to store the DP states.
**Pros:** Guarantees finding the optimal solution if one exists.; Significantly more efficient than brute-force, passing the given constraints.
**Cons:** Requires O(num) extra space for the DP table.; Slower than the optimal mathematical approach.
### Explanation
We use a 1D array, `dp`, of size `num + 1`. The state `dp[i]` represents the minimum size of the set of numbers (each ending in `k`) that sums to `i`. Our goal is to compute `dp[num]`.

We initialize `dp[0]` to 0, as an empty set has a sum of 0 and size 0. All other `dp` entries are initialized to infinity to indicate they are not yet reachable.

We then iterate from `i = 1` to `num`. For each `i`, we try to form the sum `i` by taking a previously computed sum `i - c` and adding one more number `c` to it. The number `c` must be a positive integer ending in `k`. We check all such valid `c`'s that are less than or equal to `i`. The `dp[i]` is then the minimum of `1 + dp[i - c]` over all valid `c`'s. This ensures that at each step `i`, we compute the optimal solution based on previously computed optimal solutions for smaller sums.

```java
public int minimumNumbers(int num, int k) {
    if (num == 0) {
        return 0;
    }
    int[] dp = new int[num + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int i = 1; i <= num; i++) {
        if (k == 0) {
            for (int c = 10; c <= i; c += 10) {
                if (dp[i - c] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - c]);
                }
            }
        } else {
            for (int c = k; c <= i; c += 10) {
                if (dp[i - c] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - c]);
                }
            }
        }
    }

    return dp[num] == Integer.MAX_VALUE ? -1 : dp[num];
}
```
### Algorithm
*   Create a `dp` array of size `num + 1`, where `dp[i]` will store the minimum size of a set that sums to `i`.
*   Initialize `dp[0] = 0` (an empty set sums to 0) and all other `dp[i]` to a value representing infinity (e.g., `Integer.MAX_VALUE`).
*   Iterate with an outer loop from `i = 1` to `num`.
*   Inside this loop, have an inner loop that iterates through all possible positive numbers `c` that end in `k` and are less than or equal to `i`.
*   The numbers `c` will be of the form `k, 10+k, 20+k, ...` (if `k > 0`) or `10, 20, 30, ...` (if `k = 0`).
*   For each `c`, if a solution for `dp[i - c]` exists (i.e., it's not infinity), update `dp[i]` with the formula: `dp[i] = Math.min(dp[i], 1 + dp[i - c])`.
*   After the loops complete, `dp[num]` holds the answer. If `dp[num]` is still infinity, no solution exists; return -1. Otherwise, return `dp[num]`.

## Mathematical Observation
The most efficient solution leverages a key mathematical observation about the properties of the sum. The units digit of `num` is solely determined by the number of elements in the set (`s`) and the required units digit `k`. This allows us to drastically reduce the search space and find the answer with a simple loop.
**Time:** O(1) - The loop runs a constant number of times (at most 10), regardless of the value of `num` or `k`. · **Space:** O(1) - No extra space is used that depends on the size of the input.
**Pros:** Extremely efficient with constant time and space complexity.; Simple and concise implementation.
**Cons:** The logic relies on a mathematical property that may not be immediately obvious.
### Explanation
Let the size of the set be `s`. The sum of `s` numbers, each with a units digit of `k`, must result in a number whose units digit matches `num`'s units digit. The sum of the units digits of the `s` numbers is `s * k`. Therefore, the units digit of the total sum `num` must be equal to the units digit of `s * k`. This gives us the condition: `(s * k) % 10 == num % 10`.

Furthermore, since the numbers in the set must be positive, the smallest possible number ending in `k` is `k` itself (if `k > 0`) or 10 (if `k = 0`). Thus, the smallest possible sum for a set of size `s` is `s * k` (or `s * 10` if `k=0`). This sum cannot exceed `num`, leading to the condition `s * k <= num`.

The crucial insight is that we only need to check for `s` from 1 to 10. The sequence of units digits `(s * k) % 10` is periodic and repeats every 10 values of `s`. If a solution exists with a size `s' > 10`, then a smaller solution `s = s' % 10` (or `s=10` if `s'%10==0`) would also satisfy the units digit condition while having a smaller required sum `s*k`, making it a better candidate. Therefore, if any solution exists, the minimum size must be within the range [1, 10].

This reduces the problem to a constant number of checks.

```java
public int minimumNumbers(int num, int k) {
    if (num == 0) {
        return 0;
    }

    for (int s = 1; s <= 10; s++) {
        // Check if a set of size 's' is possible.
        // 1. The sum must be large enough: s * k <= num
        // 2. The units digit must match: (s * k) % 10 == num % 10
        if (s * k <= num && (s * k) % 10 == num % 10) {
            return s;
        }
    }

    return -1;
}
```
### Algorithm
*   Handle the edge case: if `num == 0`, the size of the set is 0. Return 0.
*   Iterate through possible set sizes `s` from 1 to 10.
*   For each size `s`, check two necessary conditions:
    1.  **Sum Condition:** The sum of `s` positive numbers ending in `k` must be at least `s * k`. Therefore, we must have `s * k <= num`.
    2.  **Units Digit Condition:** The units digit of the sum of `s` numbers ending in `k` is determined by `(s * k) % 10`. This must match the units digit of `num`. So, we check if `(s * k) % 10 == num % 10`.
*   If both conditions are met for a size `s`, we have found a potential solution. Since we are iterating `s` from 1 upwards, the first `s` that satisfies both conditions is the minimum possible size. Return `s` immediately.
*   If the loop finishes (i.e., we check all sizes from 1 to 10) and no such `s` is found, it's impossible to form the sum `num`. Return -1.

# Solutions
### Java

```java
class Solution {
public
  int minimumNumbers(int num, int k) {
    if (num == 0) {
      return 0;
    }
    for (int i = 1; i <= num; ++i) {
      int t = num - k * i;
      if (t >= 0 && t % 10 == 0) {
        return i;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumNumbers(int num, int k) {
    if (num == 0)
      return 0;
    for (int i = 1; i <= num; ++i) {
      int t = num - k * i;
      if (t >= 0 && t % 10 == 0)
        return i;
    }
    return -1;
  }
};

```

### Python

```python
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

```