Nth Linear Recurrence Problem

Nth Linear Recurrence Problem — ExecCode Hard DSA Practice

Solve the Nth Linear Recurrence problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A sequence satisfies a[t] = coef[0]a[t-1] + coef[1]a[t-2] + ... for t >= k, with the first k terms given in init. The n-th term (0-based) is a linear recurrence; matrix exponentiation jumps to huge n in log time. Return a[n]. If n < k, return init[n]. You are given: coef — recurrence coefficients, length k init — first k terms n — index Return the n-th term. coef[j] multiplies a[t-1-j].

Examples

Input {'coef': [1, 1], 'init': [0, 1], 'n': 6}; Output 8. Input {'coef': [2], 'init': [3], 'n': 3}; Output 24. Input {'coef': [1, 0], 'init': [4, 5], 'n': 1}; Output 5

Constraints

k >= 1 in typical tests n >= 0

Practice Nth Linear Recurrence free on ExecCode. Browse DSA problems, topic map, and placement guides.