找到第 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

我已经用本机方法尝试过，即对于每个大于 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。

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

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

还是很容易的，不是吗？现在让我们看看你的“好”数字。我们将首先介绍函数digit_sum ( n )，它是n 中数字的总和。现在，我们不需要编写该函数；我们只需要知道它存在。这是另一个简单的问题：

3. 如果n是一个不以数字 9 结尾的数字，而s是digit_sum ( n )，那么digit_sum ( n +1) 是什么？（如果不是很清楚，请尝试几个数字。）（额外问题：为什么最后一位数字是否为 9 很重要？或者换句话说，为什么最后一位不是 9 的数字无关紧要？ 9 有什么特别之处？）

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

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

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