2310. Sum of Numbers With Units Digit K

MediumGreedyMathDynamic ProgrammingEnumeration

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 of k'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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the relationship between a tree and a graph?

A graph is a special treeA tree is a special graphNo relationshipThey are the same thing

I don’t know

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 to num inclusive. This loop represents the iteration over possible sizes of the set.
- On each iteration, we calculate t, which is num - k * i. This represents the part of the sum that is not contributed by adding numbers with unit digit k.
  - We use the walrus operator := to assign the value to t while checking the condition in the same statement.
Checking Validity of the Set:
- We check if t is non-negative and is also a multiple of 10. Both conditions are required for t to potentially be the sum of integers with the unit digit 0, which when combined with i instances of k would sum up to num.
- To check if t is a multiple of 10, we simply verify if t % 10 == 0.
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, and i is returned.
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.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Example 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 not 0, 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 to i=37 (because num = 37). In each iteration, we compute the value t as num - k * i.
Checking Validity of the Set:
- For each value of i, we want to check if t is a non-negative multiple of 10. In other words, t % 10 should be equal to 0.

Let's walk through a few iterations in our example:

i = 1: t = 37 - 8 * 1 = 29. Since 29 % 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. Since 5 % 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-negative t that is a multiple of 10 because num itself is not a multiple of 10 and k 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.

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

Not Sure What to Study? Take the 2-min Quiz：

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2310. Sum of Numbers With Units Digit K

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings