javascript - 获取模 10 序列的第 n 个元素

Question

我尝试解决以下竞赛:

Consider an infinite sequence a of decimal digits which is generated using the following algorithm:

• the first 5 digits are initially given;
• for i > 4, a[i] = (a[i - 5] + a[i - 4] + a[i - 3] + a[i - 2] + a[i - 1]) % 10, i.e. each element starting with the fifth is the sum of the previous five elements modulo 10.

我需要找到序列的第 n 个元素(第一个元素的索引为 0)。

我尝试的是:

while(a.length <= n){
    var sum = a.slice(-5).reduce((a, b) => a+b, 0);
    a.push(sum % 10);
}
return a.pop()

对于较小的 n 值，它可以工作，但当测试有大量数字(例如 521687676)时，它就不起作用。

有什么我错过的吗？我猜想可以推导出一个公式而不是循环。

Answer 1

只有 100,000 个可能的 5 位数序列，因此在某些时候任何输入都会开始重复。使用哈希来查明输入序列何时开始重复。计算周期长度。减去最大可能的完整周期并继续计算余数。

运行时间为 O(10^r)，其中 r 是序列长度。这对于较大的 r 来说很糟糕，但对于 r=5 来说很好