[Solved] Sum of Numbers With Units Digit K Contest Problem

Sum of Numbers With Units Digit K: 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.

Sum of Numbers With Units Digit K LeetCode

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

Assume the size of the set is n, and the numbers in the set are A1, A2,..., An

A1 + A2 + ... + An = sum
All numbers must have k as the unit digit
So A1 + A2 + ... + An = n*k + 10*(a1 + a2 + .. + an) = sum

Which (a1 + a2 + .. + an) can be any number.

For example:
sum = 58, k = 9 => we have n*k = 2*9 = 18, and 10*(a1 + a2) = 58 - 18 = 40. So a1 + a2 = 4

Just find the minimum number satisfying the condition (n*k)%10==sum%10

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

Since the unit's digit starts repeating after 10 iterations, it can be limited to 10. Further, the k == 0 conditionals can be removed by modifying the loop using multiplication instead of division

class Solution
{
    public int minimumNumbers(int num, int k)
    {
        if(num == 0)
            return 0;
        for(int i = 1; i*k <= num && i <= 10; i++) // Start with set size 1 and look for set having unit's digit equal to that of num
            if(num % 10 == ((i*k)%10)) // Look for equal unit's digit
                return i;
        
        return -1;
    }
}

Explanation

if num == 0, then empty set valid, return 0.

Then we enumerate the size of set from 1 to 10 and check the conditions:

The units digit of each integer is k.
The sum of the integers is num.
These two condistion equals to

size * k <= num
size * k % 10 == num % 10
Return the minimum valid size.

Complexity
Time O(1)
Space O(1)

    def minimumNumbers(self, num, k):
        if num == 0: return 0
        for i in range(1, 11):
            if k * i % 10 == num % 10 and i * k <= num:
                return i
        return -1

    int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        for (int i = 1; i * k <= num && i <= 10; ++i)
            if (k * i % 10 == num % 10)
                return i;
        return -1;
    }

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

Happy Learning – If you require any further information, feel free to contact me.