Medium

题目描述

给你两个整数 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 <= 3000
  • 0 <= k <= 9

解题思路

这个问题的关键是理解个位数字为 k 的数字的特性。如果一个数的个位数字是 k，那么这个数可以表示为 10*a + k（其中 a ≥ 0）。

核心思路：

  1. 如果 num = 0，直接返回 0（空集合）

  2. 如果 k = 0，只能使用 10, 20, 30… 这样的数字。此时只有当 num 是 10 的倍数时才有解，答案是 num/10

  3. 对于其他情况，我们需要找到最少需要多少个个位数为 k 的数字才能凑成 num

贪心策略：

  • 假设我们使用 n 个个位数为 k 的数字，那么这些数字的和的个位数字一定是 (n * k) % 10
  • 我们需要这个个位数字等于 num % 10
  • 因此需要找到最小的 n，使得 (n * k) % 10 == num % 10
  • 同时还要保证 n * k <= num（因为最小的个位数为 k 的正整数就是 k）

算法步骤：

  1. 特殊情况处理：num = 0 返回 0
  2. 如果 k = 0，检查 num 是否为 10 的倍数
  3. 枚举 n 从 1 到 10，找到满足条件的最小 n
  4. 验证 n * k <= num，如果不满足返回 -1

由于个位数字的周期性，最多只需要检查 10 个数字。

代码实现

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        
        if (k == 0) {
            return num % 10 == 0 ? num / 10 : -1;
        }
        
        for (int n = 1; n <= 10; n++) {
            if ((n * k) % 10 == num % 10 && n * k <= num) {
                return n;
            }
        }
        
        return -1;
    }
};

class Solution:
    def minimumNumbers(self, num: int, k: int) -> int:
        if num == 0:
            return 0
        
        if k == 0:
            return num // 10 if num % 10 == 0 else -1
        
        for n in range(1, 11):
            if (n * k) % 10 == num % 10 and n * k <= num:
                return n
        
        return -1

public class Solution {
    public int MinimumNumbers(int num, int k) {
        if (num == 0) return 0;
        
        if (k == 0) {
            return num % 10 == 0 ? num / 10 : -1;
        }
        
        for (int n = 1; n <= 10; n++) {
            if ((n * k) % 10 == num % 10 && n * k <= num) {
                return n;
            }
        }
        
        return -1;
    }
}

/**
 * @param {number} num
 * @param {number} k
 * @return {number}
 */
var minimumNumbers = function(num, k) {
    if (num === 0) return 0;
    
    for (let count = 1; count <= 10; count++) {
        if ((count * k) % 10 === num % 10 && count * k <= num) {
            return count;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(1)最多只需要枚举 10 次
空间复杂度O(1)只使用常量额外空间

相关题目