Nth term of a recurrence relation generated by two given arrays in Java
Nth term of a recurrence relation generated by two given arrays in Java
Given an integer N and two arrays F[] and C[] of size K, the goal is to compute the N-th term of a linear recurrence relation modulo 109 + 7. The problem requires an efficient algorithm to handle large numbers and prevent overflow. Understanding and computing recurrence relations are essential for predictive modeling and algorithmic optimizations in time-series analysis, dynamic programming, and sequence generation.
Example:
Input: F={2,1,4}, C={1,0,1}; N=6
Output: 11
Explanation: The problem involves computing the 6th term (`N = 6`) of a recurrence relation defined by initial terms `F = {2, 1, 4}` and coefficients `C = {1, 0, 1}`. By iteratively applying the recurrence relation formula F[N] = C[0] * F[N-1] + C[1] * F[N-2] + C[2] * F[N-3], the calculation for F[6] results in 11, which is obtained by modulo 10^9 + 7.
Using Naive approach
Algorithm
Step1: Checks if N is less than or equal to F's length. If so, return F[N-1] % mod.
Step 2: Initialize an array of size N to store computed terms.
Step3: Iterates from F.length to N-1 to compute each subsequent term.
Step4: Recursive relation used term[i] = ∑ F.length−1 (C[j]×terms[i−1−j]) % mod.
Step 5: Returns terms[N-1], the Nth term of the recurrence relation sequence modulo mod.
Here is an implementation of finding the nth term of a recurrence relation generated by two given arrays using a naive approach:
FileName:RecurrenceRelationNaive.java
public class RecurrenceRelationNaive {
// Function to find Nth term using a naive approach
public long findNthTermNaive(long[] F, long[] C, int N, int mod) {
// Base case: if N <= F.length, return F[N-1] % mod
if (N <= F.length) {
return F[N - 1] % mod;
}
// Calculate terms up to Nth term
long[] terms = new long[N];
for (int i = 0; i < F.length; i++) {
terms[i] = F[i] % mod;
}
for (int i = F.length; i < N; i++) {
long term = 0;
for (int j = 0; j < F.length; j++) {
term = (term + C[j] * terms[i - 1 - j] % mod) % mod;
}
terms[i] = term;
}
return terms[N - 1];
}
public static void main(String[] args) {
RecurrenceRelationNaive rr = new RecurrenceRelationNaive();
long[] F = {2, 1, 4};
long[] C = {1, 0, 1};
int N = 6;
int mod = 1000000007;
long nthTerm = rr.findNthTermNaive(F, C, N, mod);
System.out.println("Nth term of the recurrence relation: " + nthTerm);
}
}
Output:
Nth term of the recurrence relation: 11
Complexity analysis: The algorithm's time complexity is O(N * {F.length}) due to the number of iterations it performs, with a nested loop iterating over the array F.length. Its space complexity is O(N) due to the additional space required by the algorithm, primarily from the 'terms' array, which stores computed terms.
Using Optimized approach
Algorithm
Step1: Takes two square matrices, A and B, and a modulo value mod.
Step 2: Takes a square matrix M, an exponent exp, and a modulo value mod.
Step3: Initializes as an identity matrix of size n x n.
Step 4: Multiplies result by M, squares M for each iteration and halves exp.
Step 5: Takes arrays F, C, an integer N, and a modulo value mod.
Step 6: Determines array length K, creates transformation matrix T, computes T^(N-K) % mod, computes Nth term FN % mod, and returns the computed term.
Step 7: Instantiates RecurrenceRelationOpt, defines arrays F, C, N, and mod, calls findNthTerm, and prints the result.
Here is an implementation of finding the nth term of a recurrence relation generated by two given arrays using an optimized approach:
FileName:RecurrenceRelationOpt.java
import java.util.*;
public class RecurrenceRelationOpt {
// Matrix multiplication function
public long[][] matrixMultiply(long[][] A, long[][] B, int mod) {
int n = A.length;
long[][] C = new long[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = 0;
for (int k = 0; k < n; k++) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j] % mod) % mod;
}
}
}
return C;
}
// Matrix exponentiation function
public long[][] matrixExponentiate(long[][] M, int exp, int mod) {
int n = M.length;
long[][] result = new long[n][n];
// Initialize result as identity matrix
for (int i = 0; i < n; i++) {
result[i][i] = 1;
}
// Exponentiation by squaring
while (exp > 0) {
if (exp % 2 == 1) {
result = matrixMultiply(result, M, mod);
}
M = matrixMultiply(M, M, mod);
exp /= 2;
}
return result;
}
// Function to find Nth term using matrix exponentiation
public long findNthTerm(long[] F, long[] C, int N, int mod) {
int K = F.length;
// Base case: if N <= K, return F[N-1] % mod
if (N <= K) {
return F[N - 1] % mod;
}
// Create transformation matrix T
long[][] T = new long[K][K];
// Initialize the transformation matrix T based on coefficients C
for (int i = 0; i < K; i++) {
T[0][i] = C[i] % mod;
}
for (int i = 1; i < K; i++) {
T[i][i - 1] = 1;
}
// Calculate T^(N-K) % mod
T = matrixExponentiate(T, N - K, mod);
// Calculate FN % mod
long FN = 0;
for (int i = 0; i < K; i++) {
FN = (FN + T[0][i] * F[K - 1 - i] % mod) % mod;
}
return FN;
}
public static void main(String[] args) {
RecurrenceRelationOpt rr = new RecurrenceRelationOpt();
long[] F = {2, 1, 4};
long[] C = {1, 0, 1};
int N = 6;
int mod = 1000000007;
long nthTerm = rr.findNthTerm(F, C, N, mod);
System.out.println("Nth term of the recurrence relation: " + nthTerm);
}
}
Output:
Nth term of the recurrence relation: 11
Complexity analysis: The algorithm's time complexity is O(K3log(N)), where K is the length of arrays `F` and `C` due to matrix exponentiation. Space complexity is O(K^2) for storing the transformation matrix `T` and O(1) for other variables, excluding input and output space.