Sum of Numbers With Units Digit K Solution in C++

Problem Description

Ah, the classic dilemma of life: how many numbers do you need to add together to reach a specific total, while ensuring that the last digit of each number is a specific digit, say K? It’s like trying to bake a cake with a specific flavor but only having a pantry full of ingredients that don’t quite match.

Imagine you’re at a party, and everyone is bringing snacks. You want to make sure that the last snack brought is a chocolate chip cookie (because who doesn’t love cookies?). But you also want to know how many snacks you need to reach a total weight of, let’s say, 100 grams. The catch? Each snack must weigh a multiple of K grams.

In the world of LeetCode, this problem is known as “Sum of Numbers With Units Digit K.” Your task is to find the minimum number of snacks (or numbers) you need to reach the desired total weight (or number) while adhering to the last digit rule.

Code Solution

class Solution {
 public:
  int minimumNumbers(int num, int k) {
    if (num == 0)
      return 0;

    for (int i = 1; i <= 10 && i * k <= num; ++i)
      if (i * k % 10 == num % 10)
        return i;

    return -1;
  }
};

Approach

The approach taken in this solution is quite straightforward. The function checks if the number is zero, in which case it returns zero because you don’t need any numbers to sum to zero. Then, it iterates through possible counts of numbers (from 1 to 10) and checks if the sum of those numbers, which must end with the digit K, can equal the target number. If it finds a valid count, it returns that count; otherwise, it returns -1.

Time and Space Complexity

Time Complexity: O(1) - The loop runs a maximum of 10 times, which is constant time.
Space Complexity: O(1) - No additional space is used that scales with input size.

Real-World Example

Let’s say you’re at a birthday party, and you want to buy balloons. Each balloon costs $2 (K = 2), and you want to spend exactly $20 (num = 20). You could buy 10 balloons, and they all end with the digit 2. So, the answer is 10! But if you wanted to spend $25, you’d be out of luck because you can’t buy a fraction of a balloon, and the last digit wouldn’t match.