2310. Sum of Numbers With Units Digit K
Problem Description
In this problem, we are given two integers, num
and k
. We need to construct a set of positive integers that satisfy two conditions:
- The units digit (rightmost digit) of each integer in the set is
k
. - The sum of all the integers in the set is
num
.
We are asked to find the minimum possible size of such a set. If it's not possible to find any such set that satisfies the conditions, we should return -1
. It's also important to note that a set can contain multiple instances of the same integer, and an empty set has a sum of 0
.
For example, if num = 58
and k = 9
, one possible set satisfying the conditions could be {9, 9, 9, 9, 9, 9, 4}, which has a sum of 58 and each integer has a 9 as its units digit. The goal is to find the smallest such set.
Intuition
To come up with a solution, we need to first understand a few points about numbers and their units digits:
- The unit digit of a sum depends solely on the unit digits of the summands.
- Since we can have multiple instances of the same number in our set, we can think of this problem as trying to reach
num
by adding a certain number ofk's
to the multiple of 10 (since the units digit of a multiple of 10 is always 0).
The solution starts with an observation that we can keep adding the number k
until we either reach num
or we surpass it. When we add k
to itself, we keep the unit digit the same and increase the tens digit. The key insight is that if num
can be expressed as a sum of integers with a unit digit k
, then there must be a combination where the remainder when num
is divided by 10 is k
, or num
is a multiple of 10.
With this in mind, we iterate over the range from 1 to num
. For each index i
, we check if num - k * i
is a non-negative number and is also a multiple of 10 (to ensure the rest of the digits form a multiple of 10). If both conditions are met, i
is the minimum number of times we have to add k
to form part of a sum that equals num
. Therefore, i
is the smallest possible size of our desired set.
If after iterating through the possible values of i
we do not find a suitable number that meets the conditions, it means that it is not possible to form num
exclusively with numbers ending in k
, and we return -1
.
Learn more about Greedy, Math and Dynamic Programming patterns.
Solution Approach
The solution follows a straightforward brute-force approach. Since the problem requires finding the minimum number of integers required to create the sum num
, where each integer has the unit digit k
, the algorithm performs a simple iteration to check if a set can be constructed for each possible size incrementally.
Here is a breakdown of the implementation:
-
Early Return for Zero: If
num
is 0, we return 0 immediately since no number is needed to sum up to zero. -
Iteration Over Possible Set Sizes:
- We start a loop where
i
runs from 1 tonum
inclusive. This loop represents the iteration over possible sizes of the set. - On each iteration, we calculate
t
, which isnum - k * i
. This represents the part of the sum that is not contributed by adding numbers with unit digitk
.- We use the walrus operator
:=
to assign the value tot
while checking the condition in the same statement.
- We use the walrus operator
- We start a loop where
-
Checking Validity of the Set:
- We check if
t
is non-negative and is also a multiple of 10. Both conditions are required fort
to potentially be the sum of integers with the unit digit 0, which when combined withi
instances ofk
would sum up tonum
. - To check if
t
is a multiple of 10, we simply verify ift % 10 == 0
.
- We check if
-
Finding the Minimum Set Size:
- If a valid set is found (the conditions in step 3 are met), the current value of
i
represents the minimum size of the set needed, andi
is returned.
- If a valid set is found (the conditions in step 3 are met), the current value of
-
Return -1 if No Set Exists:
- If no such
i
is found after completing the loop, it indicates that it is not possible to construct such a set. Therefore, the function returns-1
.
- If no such
No complex data structures are required for this solution as it relies entirely on integer operations and a single loop. The pattern used can be identified as a brute-force search, checking all possible combinations until a valid one is found or until all options have been exhausted.
One important algorithmic insight is the leveraging of modular arithmetic to identify potential matches for the conditions set by the problem. This implementation efficiently approaches the problem with a time complexity of O(num), where num
is the integer representing the sum we are trying to reach.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example where num = 37
and k = 8
.
Following the provided steps:
-
Early Return for Zero: Since
num
is not0
, we do not return immediately and continue with the iterative process. -
Iteration Over Possible Set Sizes:
- We start the loop with
i=1
and go up toi=37
(becausenum = 37
). In each iteration, we compute the valuet
asnum - k * i
.
- We start the loop with
-
Checking Validity of the Set:
- For each value of
i
, we want to check ift
is a non-negative multiple of 10. In other words,t % 10
should be equal to0
.
- For each value of
Let's walk through a few iterations in our example:
-
i = 1
:t = 37 - 8 * 1 = 29
. Since29 % 10 ā 0
, the set {8} with size 1 is not enough. -
i = 2
:t = 37 - 8 * 2 = 21
. Again,21 % 10 ā 0
, so the set {8, 8} with size 2 is not enough. -
...
-
Continuing this process, we finally reach:
-
i = 4
:t = 37 - 8 * 4 = 5
. Since5 % 10 ā 0
, even the set {8, 8, 8, 8} with size 4 does not meet the requirement. -
...
-
We reach
i = 5
:t = 37 - 8 * 5 = 37 - 40 = -3
. This is a negative number, so it is evident that the set with multiple 8s that add up to 37 does not exist. We will never find a non-negativet
that is a multiple of 10 becausenum
itself is not a multiple of 10 andk
does not have a unit digit that could make up the difference.
-
Finding the Minimum Set Size:
- Since none of our checks for a valid set has passed, we don't have a minimum size to return.
-
Return -1 if No Set Exists:
- Since the loop has finished and no non-negative multiple of 10 was found for
t
, we return-1
.
- Since the loop has finished and no non-negative multiple of 10 was found for
Thus, in this example, we can't find a set consisting of positive integers with the unit digit k
(which is 8) that sums up to num
(which is 37). The smallest possible set does not exist, hence the return value is -1
.
Solution Implementation
1class Solution:
2 def minimumNumbers(self, num: int, k: int) -> int:
3 # If num is 0, no number needs to be added, so return 0
4 if num == 0:
5 return 0
6
7 # Iterate through i from 1 up to the given number
8 for i in range(1, num + 1):
9 # Calculate the remaining value after subtracting i times k from num
10 remaining_value = num - k * i
11
12 # Check if remaining value is non-negative and divisible by 10
13 if remaining_value >= 0 and remaining_value % 10 == 0:
14 # If both conditions are met, i is the minimum count of numbers needed
15 return i
16
17 # If no such number exists that the remaining value is divisible by 10, return -1
18 return -1
19
1class Solution {
2
3 // Method to find the minimum number of non-negative integers needed
4 // where the last digit of each integer is 'k', and their sum is 'num'.
5 public int minimumNumbers(int num, int k) {
6 // If the sum required is 0, no numbers are needed.
7 if (num == 0) {
8 return 0;
9 }
10
11 // Iterate from 1 to 'num' to find the minimum count of integers needed.
12 for (int i = 1; i <= num; ++i) {
13 // Calculate the remaining value after subtracting 'k * i'.
14 int remainder = num - k * i;
15
16 // If the remainder is non-negative and ends with a 0,
17 // it means we found a valid group of 'i' numbers that sum up to 'num'.
18 if (remainder >= 0 && remainder % 10 == 0) {
19 return i; // Return the count 'i' as the result.
20 }
21 }
22
23 // If no valid combination is found, return -1.
24 return -1;
25 }
26}
27
1class Solution {
2public:
3 // Function to find the minimum number of integers needed whose last digit is 'k'
4 // that add up to the number 'num'
5 int minimumNumbers(int num, int k) {
6 // If num is 0, no numbers are needed, so return 0.
7 if (num == 0) {
8 return 0;
9 }
10
11 // Iterate over possible counts of numbers with last digit 'k'
12 for (int count = 1; count <= num; ++count) {
13 // Calculate the remaining value after subtracting 'count' numbers
14 // with last digit 'k'
15 int remainder = num - k * count;
16
17 // If the remainder is non-negative and is a multiple of 10,
18 // it means the number can be formed by 'count' numbers ending with 'k'
19 if (remainder >= 0 && remainder % 10 == 0) {
20 return count; // Return the count as the answer
21 }
22 }
23
24 // If it's not possible to sum to 'num' with integers ending in 'k', return -1
25 return -1;
26 }
27};
28
1// This function finds the minimum number of integers needed to sum up to a given number 'num',
2// where each integer must end with the digit 'k'.
3function minimumNumbers(num: number, k: number): number {
4 // If 'num' is 0, no numbers are needed so return 0.
5 if (num === 0) {
6 return 0;
7 }
8
9 // Determine the last digit of 'num'.
10 let lastDigit = num % 10;
11
12 // Check every possible integer with the last digit 'k'.
13 for (let i = 1; i <= 10; i++) {
14 let currentNumber = i * k;
15 // The maximum number of integers with the last digit 'k' that we would need is 10,
16 // as every digit from 0 to 9 will have appeared with 'k' at least once.
17 // If 'currentNumber' is less than or equal to 'num' and ends with the same digit as 'num',
18 // it's possible to sum up to 'num' with 'i' numbers ending with 'k'.
19 if (currentNumber <= num && currentNumber % 10 === lastDigit) {
20 return i;
21 }
22 }
23
24 // If no such number could be found within the range, return -1 to indicate failure.
25 return -1;
26}
27
Time and Space Complexity
The time complexity of the given code is O(num)
because the loop runs a maximum of num
iterations. In each iteration, it performs constant-time operations such as arithmetic subtraction, multiplication, and modulus operation. Therefore, the upper bound of loop iterations directly scales with the value of num
.
The space complexity of the code is O(1)
because the space used does not depend on the size of the input num
. The algorithm uses a fixed number of variables (i
and t
) that do not scale with input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!