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:

• 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.

I need to find the nth element of the sequence (the first element has index 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).

Is anything I missed it ? I guess that it can be deduced a formula instead of loops.

Answer 1

There are only 100,000 possible 5 digit sequences, so at some point any input will start repeating. 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. This is bad for large r but fine for r=5