javascript - 获取模10序列的第n个元素(Get n-th element of modulo 10 sequence)

Question

I tried to solve the following contest:(我试图解决以下竞赛：)

Consider an infinite sequence a of decimal digits which is generated using the following algorithm:(考虑使用以下算法生成的无穷十进制数字a：) the first 5 digits are initially given;(最初给出的前5位数字；) for i > 4, a[i] = (a[i - 5] + a[i - 4] + a[i - 3] + a[i - 2] + a[i - 1]) % 10 , ie each element starting with the fifth is the sum of the previous five elements modulo 10.(对于i > 4, a[i] = (a[i - 5] + a[i - 4] + a[i - 3] + a[i - 2] + a[i - 1]) % 10 ，即从第五个元素开始的每个元素都是前五个元素的模数之和为10。) I need to find the nth element of the sequence (the first element has index 0).(我需要找到序列的第n个元素（第一个元素的索引为0）。) What I tried is:(我试过的是：) while(a.length <= n){ var sum = a.slice(-5).reduce((a, b) => a+b, 0); a.push(sum % 10); } return a.pop() For small n values it works but it's not working when the tests have large numbers(like 521687676).(对于较小的n值，它可以工作，但是在测试有大量数字（例如521687676）时不起作用。) Is anything I missed it ?(我有什么想念的吗？) I guess that it can be deduced a formula instead of loops.(我猜可以推导出公式而不是循环。)   ask by Mihai Alexandru-Ionut translate from so

Answer 1

There are only 100,000 possible 5 digit sequences, so at some point any input will start repeating.(只有100,000个可能的5位数字序列，因此在某个时候任何输入都会开始重复。)

Use a hash to find out when your input sequence has started repeating.(使用散列找出输入序列何时开始重复。) Calculate the cycle length.(计算循环长度。) Subtract the max possible full cycles and continue with the remainder.(减去最大可能的完整循环，然后继续其余的循环。) Running time is O(10^r) where r is the sequence length.(运行时间为O（10 ^ r），其中r是序列长度。) This is bad for large r but fine for r=5(这对大r不利，但对r = 5有利)