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 _theminimum 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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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

1
2
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

Approach

We want the minimum number of positive integers with units digit k that sum to num. Try all possible counts x (from 1 to 300, since num <= 3000), and check if num - k * x is non-negative and divisible by 10. If so, x is a valid answer. Return the smallest such x, or 0 if num == 0, or -1 if not possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        for (int x = 1; x <= 300; ++x) {
            if (num - k * x < 0) break;
            if ((num - k * x) % 10 == 0) return x;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        for (int x = 1; x <= 300; ++x) {
            if (num - k * x < 0) break;
            if ((num - k * x) % 10 == 0) return x;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun minimumNumbers(num: Int, k: Int): Int {
        if (num == 0) return 0
        for (x in 1..300) {
            if (num - k * x < 0) break
            if ((num - k * x) % 10 == 0) return x
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        for x in range(1, 301):
            if num - k * x < 0:
                break
            if (num - k * x) % 10 == 0:
                return x
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn minimum_numbers(num: i32, k: i32) -> i32 {
        if num == 0 { return 0; }
        for x in 1..=300 {
            if num - k * x < 0 { break; }
            if (num - k * x) % 10 == 0 { return x; }
        }
        -1
    }
}
1
2
3
4
5
6
7
8

function minimumNumbers(num: number, k: number): number {
    if (num === 0) return 0;
    for (let x = 1; x <= 300; ++x) {
        if (num - k * x < 0) break;
        if ((num - k * x) % 10 === 0) return x;
    }
    return -1;
}

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)