Consider a sequence {x_{0}, x_{1}, x_{2}, ...}. A relation that defines some term x_{n} in terms of previous terms is called a recurrence relation. A linear recurrence relation is one where the recurrence is of the form x_{n} = c_{k-1}x_{n-1} + c_{k-2}x_{n-2} + ... + c_{0}x_{n-k}, where all the c_{i} are real-valued constants, k is the length of the recurrence relation, and n is an arbitrary positive integer which is greater than or equal to k.
You will be given a int[] **coefficients**, indicating, in order, c_{0}, c_{1}, ..., c_{k-1}. You will also be given a int[] **initial**, giving the values of x_{0}, x_{1}, ..., x_{k-1}, and an int **N**. Your method should return x_{N} modulo 10.
Note that the value of X modulo 10 equals the last digit of X if X is non-negative. However, if X is negative, this is *not* true; instead, X modulo 10 equals ((10 - ((-X) modulo 10)) modulo 10). For example, (-16) modulo 10 = ((10 - (16 modulo 10)) modulo 10) = (10 - 6) modulo 10 = 4.
More specifically, if **coefficients** is of size *k*, then the recurrence relation will be
- x
_{n} = coefficients[k - 1] * x_{n-1} + coefficients[k - 2] * x_{n-2} + ... + coefficients[0] * x_{n-k}.
For example, if **coefficients** = {2,1}, **initial** = {9,7}, and **N** = 6, then our recurrence relation is x_{n} = x_{n-1} + 2 * x_{n-2} and we have x_{0} = 9 and x_{1} = 7. Then x_{2} = x_{1} + 2 * x_{0} = 7 + 2 * 9 = 25, and similarly, x_{3} = 39, x_{4} = 89, x_{5} = 167, and x_{6} = 345, so your method would return (345 modulo 10) = 5. |