2310. Sum of Numbers With Units Digit K

Problem Description

Given two integers num and k, we need to find the minimum number of positive integers whose units digit is k and sum up to num. If no such set exists, return -1.

Solution Explanation

The most efficient approach is a mathematical one leveraging the properties of units digits. Let's break down the logic:

1. Base Cases:

   • If num is 0, the minimum size is 0 (empty set).
   • If k is 0 and num is not a multiple of 10, it's impossible, so return -1. If k is 0 and num is a multiple of 10, we need only one number (which is num).

2. Units Digit Matching: The core idea is to focus on the units digit of num. We need the sum of units digits of the numbers in the set to match the units digit of num. Since each number's units digit is k, the total contribution to the units digit from n numbers is (n * k) % 10. This must equal num % 10.

3. Iteration: We iterate through possible values of n (number of integers in the set), starting from 1. For each n, we check if (n * k) % 10 == num % 10. If it does, we check if n * k <= num. If true, n is a possible candidate. We don't need to check higher n.

4. Result: If we find such an n, it's the minimum size of the set. Otherwise, no such set exists, and we return -1.

Time and Space Complexity Analysis

• Time Complexity: O(min(num, 10)). The loop iterates at most 10 times (or up to num, whichever is smaller). The operations inside the loop are constant time.
• Space Complexity: O(1). We use only a few constant extra variables.

Code Implementation (Python)

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        if k == 0:
            return -1 if num % 10 else 1  # Handle k=0 case
 
        for n in range(1, 11):  # Iterate up to 10 (sufficient)
            if (n * k) % 10 == num % 10 and n * k <= num:
                return n
        return -1
 

Code Implementation (Java)

class Solution {
    public int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        if (k == 0) return (num % 10 == 0) ? 1 : -1; //Handle k=0 case
 
        for (int n = 1; n <= 10; ++n) {
            if ((n * k) % 10 == num % 10 && n * k <= num) {
                return n;
            }
        }
        return -1;
    }
}

Code Implementation (C++)

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        if (k == 0) return (num % 10 == 0) ? 1 : -1; //Handle k=0 case
 
        for (int n = 1; n <= 10; ++n) {
            if ((n * k) % 10 == num % 10 && (long long)n * k <= num) {
                return n;
            }
        }
        return -1;
    }
};

Note: The C++ version uses (long long) to avoid potential integer overflow when multiplying n and k. This is a crucial detail for handling larger inputs. Other languages might not require explicit casting if their integer types have sufficient range.

The provided solutions are concise and highly efficient due to the mathematical insight. They avoid unnecessary computations and handle edge cases properly. The time complexity is significantly better than brute-force approaches that would try to enumerate all possible combinations of numbers.