Skip to content

2310. Sum of Numbers With Units Digit K

SourceWeekly Contest 298 Q2DifficultyMediumRating1558

Description

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

Solutions

Solution 1: Math + Enumeration

Thinking

Each addend is \(10x+k\), so the units digit of a sum of \(n\) such numbers is determined by \(n\times k\). \(num \le 3000\), so we enumerate \(n\) and test whether \(num-n\times k\) is a non-negative multiple of \(10\).

Try \(n\) from small to large; the first success is minimal. If none works up to \(num\), there is no solution.

Each number that meets the splitting condition can be represented as \(10x_i + k\). If there are \(n\) such numbers, then \(\textit{num} - n \times k\) must be a multiple of \(10\).

We enumerate \(n\) from small to large, and find the first \(n\) that satisfies \(\textit{num} - n \times k\) being a multiple of \(10\). Since \(n\) cannot exceed \(\textit{num}\), the maximum value of \(n\) is \(\textit{num}\).

We can also only consider the units digit. If the units digit satisfies the condition, the higher digits can be arbitrary.

The time complexity is \(O(n)\), where \(n\) is the size of \(\textit{num}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        for i in range(1, num + 1):
            if (t := num - k * i) >= 0 and t % 10 == 0:
                return i
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func minimumNumbers(num int, k int) int {
    if num == 0 {
        return 0
    }
    for i := 1; i <= num; i++ {
        t := num - k*i
        if t >= 0 && t%10 == 0 {
            return i
        }
    }
    return -1
}

1
2
3
4
5
6
7
8
9
function minimumNumbers(num: number, k: number): number {
    if (!num) return 0;
    let digit = num % 10;
    for (let i = 1; i < 11; i++) {
        let target = i * k;
        if (target <= num && target % 10 == digit) return i;
    }
    return -1;
}

Solution 2: Math + Enumeration (Units Digit)

Thinking

Method 1 may try up to \(num\) values. Units digits repeat every \(10\), so it suffices to test \(n \le 10\) with \(n\times k\) congruent to \(num\) and at most \(num\).

Enumerate at most \(10\) numbers whose units digit is \(k\).

1
2
3
4
5
6
7
8
class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        for i in range(1, 11):
            if (k * i) % 10 == num % 10 and k * i <= num:
                return i
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minimumNumbers(int num, int k) {
        if (num == 0) {
            return 0;
        }
        for (int i = 1; i <= 10; ++i) {
            if ((k * i) % 10 == num % 10 && k * i <= num) {
                return i;
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (!num) return 0;
        for (int i = 1; i <= 10; ++i)
            if ((k * i) % 10 == num % 10 && k * i <= num)
                return i;
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minimumNumbers(num int, k int) int {
    if num == 0 {
        return 0
    }
    for i := 1; i <= 10; i++ {
        if (k*i)%10 == num%10 && k*i <= num {
            return i
        }
    }
    return -1
}

Thinking

The first two methods lean on divisibility and are compact, but do not extend if more constraints appear. Memoized search subtracts numbers with units digit \(k\); subproblems depend only on the remainder. It is correct here, yet heavier than direct enumeration.

Memoize the fewest numbers with units digit \(k\) that sum to \(\textit{num}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        @cache
        def dfs(v):
            if v == 0:
                return 0
            if v < 10 and v % k:
                return inf
            i = 0
            t = inf
            while (x := i * 10 + k) <= v:
                t = min(t, dfs(v - x))
                i += 1
            return t + 1

        if num == 0:
            return 0
        if k == 0:
            return -1 if num % 10 else 1
        ans = dfs(num)
        return -1 if ans >= inf else ans

Comments