LeetCode 题解工作台
个位数字为 K 的整数之和
给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集： 每个整数个位数字都是 k 。 所有整数之和是 num 。 返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。 注意： 多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。 个位数字 是数字最右边的数位。 …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
符合拆分条件的每个数都可以表示成 ，若总共有 个数，那么 $\textit{num}-n \times k$ 必然是 的倍数。 我们从小到达枚举 ，找到第一个满足 $\textit{num}-n \times k$ 是 的倍数的 。由于 不会超过 ，因此 最大枚举至 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集：
- 每个整数个位数字都是
k。 - 所有整数之和是
num。
返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。
注意：
- 多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为
0。 - 个位数字 是数字最右边的数位。
示例 1：
输入：num = 58, k = 9 输出：2 解释： 多重集 [9,49] 满足题目条件，和为 58 且每个整数的个位数字是 9 。 另一个满足条件的多重集是 [19,39] 。 可以证明 2 是满足题目条件的多重集的最小长度。
示例 2：
输入：num = 37, k = 2 输出：-1 解释：个位数字为 2 的整数无法相加得到 37 。
示例 3：
输入：num = 0, k = 7 输出：0 解释：空多重集的和为 0 。
提示：
0 <= num <= 30000 <= k <= 9
解题思路
方法一：数学 + 枚举
符合拆分条件的每个数都可以表示成 ，若总共有 个数，那么 必然是 的倍数。
我们从小到达枚举 ，找到第一个满足 是 的倍数的 。由于 不会超过 ，因此 最大枚举至 。
也可以只考虑个位，个位满足，高位随意。
时间复杂度 ，其中 为 的大小。空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(num/k) in greedy checks to O(num) in DP. Space complexity depends on memoization or DP table size, which is O(num). Recursive approaches may use stack space up to O(num/k). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate quickly identifies units digit pattern for recursion or DP.
- question_mark
Candidate evaluates minimal set size instead of arbitrary sums.
- question_mark
Candidate handles edge cases: zero sum and impossible sums correctly.
常见陷阱
外企场景- error
Ignoring sums where multiple combinations yield smaller counts.
- error
Failing to handle num = 0 as an empty set.
- error
Misapplying greedy without checking all remainder possibilities, leading to wrong -1 results.
进阶变体
外企场景- arrow_right_alt
Find minimum set with digits ending in k summing to a target multiple of 10.
- arrow_right_alt
Allow negative integers with units digit k and sum to num.
- arrow_right_alt
Count all possible sets meeting the units digit condition instead of minimum size.