Scale Engineer

Sum of Numbers With Units Digit K

Med
#2105Time: Exponential - O(c^N) where N is `num` and c is the number of choices at each step. The function branches for every possible number ending in `k`, leading to an exponential number of calls.Space: O(num) - The maximum depth of the recursion stack can be proportional to `num` in the worst case (e.g., if `k=1` and we keep subtracting 11, 21, etc.).
Patterns
MathDynamic ProgrammingGreedyEnumeration

Prompt

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.

 

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring all possible combinations of numbers that end in k to see if they can sum up to num. A recursive function is defined to try subtracting every possible valid number (e.g., k, 10+k, 20+k, etc.) from the target num and finding the minimum count of numbers used in this process.

Algorithm

  • Define a recursive function solve(target) that returns the minimum number of integers ending in k that sum to target.
  • Base Case 1: If target == 0, it means we have successfully formed the sum, so we need 0 more numbers. Return 0.
  • Base Case 2: If target < 0, it's an invalid path. Return a value indicating impossibility, like Integer.MAX_VALUE.
  • Recursive Step: Initialize a variable minSize to Integer.MAX_VALUE.
  • Iterate through all possible positive integers c that end with digit k and are less than or equal to the current target (e.g., k, 10+k, 20+k, ... or 10, 20, ... if k=0).
  • For each c, make a recursive call solve(target - c).
  • If the recursive call does not return Integer.MAX_VALUE, it means a solution was found for the subproblem. Update minSize = Math.min(minSize, 1 + solve(target - c)).
  • Return minSize.
  • The initial call is solve(num). If the result is Integer.MAX_VALUE, it means no solution exists, so return -1.

Walkthrough

The core idea is to use a recursive function, let's call it solve(target), which calculates the minimum number of items to reach a target sum. The function works as follows:

  1. If the target is 0, it means we've found a valid combination, and the size of this sub-solution is 0. We return 0.
  2. If the target becomes negative, it means the last number we subtracted was too large, so this path is invalid. We return an indicator of failure, such as infinity.
  3. For a positive target, we iterate through all valid numbers c that we can use (positive integers ending in k). For each c, we recursively call solve(target - c). We are looking for the minimum result among 1 + solve(target - c) over all possible choices of c.

This method is a classic brute-force search. It explores the entire search space, but because it recalculates solutions for the same target values multiple times, its performance is very poor.

Complexity

Time

Exponential - O(c^N) where N is `num` and c is the number of choices at each step. The function branches for every possible number ending in `k`, leading to an exponential number of calls.

Space

O(num) - The maximum depth of the recursion stack can be proportional to `num` in the worst case (e.g., if `k=1` and we keep subtracting 11, 21, etc.).

Trade-offs

Pros

  • Conceptually simple and a direct translation of the problem statement.

Cons

  • Extremely inefficient due to re-computation of the same subproblems.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem