algorithm - 找到第 k 个好数

Question

最近，在竞争性编码考试中，我得到了这个问题 -

一个好数字是指其数字之和能被 5 整除的数字。示例 - 5 (5), 14 (1+4), 19(1+9), 23(2+3)

问题是——你得到了一个整数 n和另一个整数 k你必须找到大于 n 的第 k 个好数。

约束 - 1<k<10^9

样本测试 1 -

input: n = 6, k = 5
output: 32
Explanation: After 6 good numbers are  - 14, 19, 23, 28, 32 (5th is 32)

样本测试 2 -

input: n = 5, k = 1
output: 14
Explanation: 5 is 1st good number but we need greater than 5 so ans is 14

我已经尝试使用 native 方法，即对于每个大于 n 的数字，检查它是否正确并循环直到我找到 k 个正确的数字，这是我的代码 -

def solve(n,k):
    n+=1
    count = 0
    while count<k:
        if sum(map(int,str(n)))%5==0:
            count+=1
        n+=1
    return n-1

但上面的代码给了我 TLE，如何以更好的时间复杂度来完成它，我在互联网上搜索过类似的问题但无法找到帮助。

Answer 1

让我们从一个简单的问题开始:

1. 我给你一个包含五个连续 数字的列表。这些数字中有多少可以被 5 整除？ (我不是在谈论数字的总和。只是数字，例如 18、19、20、21、22。

没问题吧？所以一个稍微不同的问题:

1. 在十个连续数字的列表中，有多少个可以被 5 整除？

仍然很简单，不是吗？现在让我们看看你的“好”数字。我们将从介绍函数 digit_sum(n) 开始，它是 n 中数字的总和。现在，我们不需要编写那个函数；我们只需要知道它存在。这是另一个简单的问题:

1. 如果 n 是一个不以数字 9 结尾的数字并且 s 是 digit_sum(n )，什么是 digit_sum(n+1)？ (如果不是很清楚，请尝试几个数字。)(额外问题:为什么最后一位数字是 9 很重要？或者换句话说，为什么末尾不是 9 的数字不重要？ 9 有什么特别之处？)

好的，差不多了。让我们把这两个想法放在一起:

1. 假设n以0结尾，十个数digit_sum(n)中有多少个，digit_sum( n+1), digit_sum(n+2), ... digit_sum(n+9) 能被 5 整除？ (见问题 2)。

这是否能帮助您找到一种快速计算 n 后第 k 个好数的方法？希望答案是肯定的。现在您只需要概括一下。