Sum of Numbers With Units Digit K

Problem Description

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.

Key Insights

• The units digit of the integers must match k.
• If num is less than k, it is impossible to form a valid set.
• A valid integer can be represented as 10 * x + k where x is a non-negative integer.
• The minimum size of the set can be determined based on how many times we can use integers ending with k to reach the sum num.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To solve this problem, we can use a greedy approach. The strategy is as follows:

1. Check if num is less than k. If so, return -1 since it's impossible to form a valid set.
2. Calculate the remainder of num when divided by 10. This will help us determine if num can be represented using integers ending with k.
3. If the remainder matches k, we can use integers of the form k, (10 + k), (20 + k), etc.
4. The number of such integers needed is (num - k) / 10 + 1 if num is greater than or equal to k.
5. If num is smaller than k and not equal to 0, return -1. If num is 0, return 0 since the sum of an empty set is valid.

Code Solutions