Problem Description

Given three integers num, k, and n, the task is to find the minimum number of positive integers (not necessarily distinct) such that:

• The sum of these integers is exactly num.
• Each integer is a positive multiple of k (i.e., each integer ends with the digit k).
• You can use as many numbers as needed, but you want to use as few as possible.

Constraints:

• 1 ≤ num ≤ 10⁹
• 0 ≤ k ≤ 9

Thought Process

Let's break down the problem. We are asked to split num into the smallest number of positive integers, each ending with digit k (i.e., each is of the form m * 10 + k for some integer m ≥ 0).

The brute-force way would be to try all combinations of such numbers, but that's computationally infeasible for large num. Instead, let's look for patterns:

• Any number ending with k can be written as k, k+10, k+20, ...
• If we use i such numbers, their sum is i*k + 10*(a1 + a2 + ... + ai), where each ai ≥ 0.
• But since the numbers can be repeated, we can just use i times k plus some multiple of 10.
• So, for each possible i, check if num - i*k is a non-negative multiple of 10.

Solution Approach

Let's formalize the approach step by step:

1. For i from 1 up to a reasonable limit (since k is a single digit, i won't need to be large—at most 100 is sufficient):
   • Calculate total = num - i * k.
   • If total is negative, break (since adding more ks will only make it more negative).
   • If total is divisible by 10 (i.e., total % 10 == 0), then i is the minimal number of numbers needed.
2. If no such i is found, return -1.

Why does this work? Because any number ending with k is congruent to k mod 10. The sum of i such numbers is congruent to i*k mod 10. So, we want num to be congruent to i*k mod 10, and the remainder should be made up by sums of 10s (i.e., multiples of 10).

Example Walkthrough

Example: num = 58, k = 9

• Try i = 1: 58 - 1*9 = 49, 49 % 10 = 9 (not 0)
• Try i = 2: 58 - 2*9 = 40, 40 % 10 = 0 (Success!)

So, the answer is 2. We can use two numbers ending in 9 (e.g., 9 and 49, or 19 and 39, etc.) that sum to 58.

Another Example: num = 37, k = 2

• i = 1: 37-2=35, 35%10=5
• i = 2: 37-4=33, 33%10=3
• i = 3: 37-6=31, 31%10=1
• i = 4: 37-8=29, 29%10=9
• i = 5: 37-10=27, 27%10=7
• i = 6: 37-12=25, 25%10=5
• ... and so on, none will ever be 0.

Time and Space Complexity

Brute-force Approach: Would try all possible combinations of numbers ending with k that sum to num, which is exponential in num and not feasible.

Optimized Approach:

• We iterate i from 1 up to at most 100 (since the last digit cycles every 10, and we need to ensure that i*k covers all possible remainders mod 10).
• So, the time complexity is O(1) (constant), since the loop is capped at a small number regardless of num.
• Space complexity is O(1) as we only use a few variables.

Summary

The key insight is that the sum of numbers ending with k can be represented as i*k plus a multiple of 10. By iterating over possible counts i, we check if num - i*k is a non-negative multiple of 10. This approach is efficient, easy to implement, and leverages properties of modular arithmetic to avoid brute-force enumeration.

Code Implementation

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

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

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

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