We all know that Fibonacci numbers (Fn) are defined by the recurrence relation
Fibonacci Numbers (Fn) = F(n-1) + F(n-2)
with seed values
F0 = 0 and F1 = 1
Similarly, we can generalize these numbers. Such a number sequence is known as Generalized Fibonacci number (G).
Generalized Fibonacci number (G) is defined by the recurrence relation
Generalized Fibonacci Numbers (Gn) = (c * G(n-1)) + (d * G(n-2))
with seed values
G0 = a and G1 = b
Finding Nth term
Given the four constant values of Generalized Fibonacci Numbers as a, b, c, and d and an integer N, the task is to find the Nth term of the Generalized Fibonacci Numbers, i.e. Gn.
Examples:
Input: N = 2, a = 0, b = 1, c = 2, d = 3
Output: 2
Explanation:
As a = 0 -> G(0) = 0
b = 1 -> G(1) = 1
So, G(2) = 2 * G(1) + 3 * G(0) = 2Input: N = 3, a = 0, b = 1, c = 2, d = 3
Output: 7
Naive Approach: Using the given values, find each term of the series till the Nth term and then print the Nth term.
Time Complexity: O(2N)
Another Approach: The idea is to use DP tabulation to find all the terms till the Nth terms and then print the Nth term.
Time Complexity: O(N)
Efficient Approach: Using matrix multiplication we can solve the given problem in log(N) time.
Below is the implementation of the above approach:
C++
// C++ program to implement the // Generalised Fibonacci numbers #include <bits/stdc++.h> using namespace std; // Helper function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] void multiply(int F[2][2], int M[2][2]); // Helper function that calculates F[][] // raised to the power N // and puts the result in F[][] void power(int F[2][2], int N, int m, int n); // Function to find the Nth term int F(int N, int a, int b, int m, int n) { // m 1 // n 0 int F[2][2] = { { m, 1 }, { n, 0 } }; if (N == 0) return a; if (N == 1) return b; if (N == 2) return m * b + n * a; int initial[2][2] = { { m * b + n * a, b }, { b, a } }; power(F, N - 2, m, n); // Discussed above multiply(initial, F); return F[0][0]; } // Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] void multiply(int F[2][2], int M[2][2]) { int x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; int y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; int z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; int w = F[1][0] * M[0][1] + F[1][1] * M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } // Function that calculates F[][] // raised to the power N // and puts the result in F[][] void power(int F[2][2], int N, int m, int n) { int i; int M[2][2] = { { m, 1 }, { n, 0 } }; for (i = 1; i <= N; i++) multiply(F, M); } // Driver code int main() { int N = 2, a = 0, b = 1, m = 2, n = 3; printf("%d\n", F(N, a, b, m, n)); N = 3; printf("%d\n", F(N, a, b, m, n)); N = 4; printf("%d\n", F(N, a, b, m, n)); N = 5; printf("%d\n", F(N, a, b, m, n)); return 0; } |
Java
// Java program to implement the // Generalised Fibonacci numbers import java.util.*;class GFG{// Function to find the Nth term static int F(int N, int a, int b, int m, int n) { // m 1 // n 0 int[][] F = { { m, 1 }, { n, 0 } }; if (N == 0) return a; if (N == 1) return b; if (N == 2) return m * b + n * a; int[][] initial = { { m * b + n * a, b }, { b, a } }; power(F, N - 2, m, n); // Discussed below multiply(initial, F); return F[0][0]; } // Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] static void multiply(int[][] F, int[][] M) { int x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; int y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; int z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; int w = F[1][0] * M[0][1] + F[1][1] * M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } // Function that calculates F[][] // raised to the power N // and puts the result in F[][] static void power(int[][] F, int N, int m, int n) { int i; int[][] M = { { m, 1 }, { n, 0 } }; for(i = 1; i <= N; i++) multiply(F, M); } // Driver codepublic static void main(String[] args){ int N = 2, a = 0, b = 1, m = 2, n = 3; System.out.println(F(N, a, b, m, n)); N = 3; System.out.println(F(N, a, b, m, n)); N = 4; System.out.println(F(N, a, b, m, n)); N = 5; System.out.println(F(N, a, b, m, n)); }}// This code is contributed by offbeat |
Python3
# Python3 program to implement the# Generalised Fibonacci numbers# Function to find the Nth termdef F(N, a, b, m, n): # m 1 # n 0 F = [[ m, 1 ], [ n, 0 ]] if(N == 0): return a if(N == 1): return b if(N == 2): return m * b + n * a initial = [[ m * b + n * b, b ], [ b, a ]] power(F, N - 2, m, n) multiply(initial, F) return F[0][0]# Function that multiplies# 2 matrices F and M of size 2*2,# and puts the multiplication# result back to F[][]def multiply(F, M): x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) F[0][0] = x F[0][1] = y F[1][0] = z F[1][1] = w# Function that calculates F[][]# raised to the power N# and puts the result in F[][]def power(F, N, m, n): M = [[ m, 1 ], [ n, 0 ]] for i in range(1, N + 1): multiply(F, M)# Driver codeif __name__ == '__main__': N, a, b, m, n = 2, 0, 1, 2, 3 print(F(N, a, b, m, n)) N = 3 print(F(N, a, b, m, n)) N = 4 print(F(N, a, b, m, n)) N = 5 print(F(N, a, b, m, n))# This code is contributed by Shivam Singh |
C#
// C# program to implement the // Generalised Fibonacci numbers using System;class GFG{ // Function to find the Nth term static int F(int N, int a, int b, int m, int n) { // m 1 // n 0 int[,] F = { { m, 1 }, { n, 0 } }; if (N == 0) return a; if (N == 1) return b; if (N == 2) return m * b + n * a; int[,] initial = { { m * b + n * a, b }, { b, a } }; power(F, N - 2, m, n); // Discussed below multiply(initial, F); return F[0, 0]; } // Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[,] static void multiply(int[,] F, int[,] M) { int x = F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0]; int y = F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1]; int z = F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0]; int w = F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1]; F[0, 0] = x; F[0, 1] = y; F[1, 0] = z; F[1, 1] = w; } // Function that calculates F[,] // raised to the power N // and puts the result in F[,] static void power(int[,] F, int N, int m, int n) { int i; int[,] M = { { m, 1 }, { n, 0 } }; for(i = 1; i <= N; i++) multiply(F, M); } // Driver codepublic static void Main(String[] args){ int N = 2, a = 0, b = 1, m = 2, n = 3; Console.WriteLine(F(N, a, b, m, n)); N = 3; Console.WriteLine(F(N, a, b, m, n)); N = 4; Console.WriteLine(F(N, a, b, m, n)); N = 5; Console.WriteLine(F(N, a, b, m, n)); }} // This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to implement the // Generalised Fibonacci numbers // Function to find the Nth term function F(N, a, b, m, n){ var F = [ [ m, 1 ], [ n, 0 ] ] if (N == 0) return a; if (N == 1) return b; if (N == 2) return m * b + n * a; var initial = [ [ m * b + n * a, b ], [ b, a ] ] power(F, N - 2, m, n); // Discussed below multiply(initial, F); return F[0][0]; }// Function that multiplies // 2 matrices F and M of size 2*2, // and puts the multiplication // result back to F[][] function multiply(F, M) { var x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; var y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; var z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; var w = F[1][0] * M[0][1] + F[1][1] * M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } // Function that calculates F[][] // raised to the power N // and puts the result in F[][] function power(F, N, m, n) { var i; var M = [ [ m, 1 ], [ n, 0 ] ]; for(i = 1; i <= N; i++) multiply(F, M); } // Driver codevar N = 2, a = 0, b = 1, m = 2, n = 3;document.write(F(N, a, b, m, n) + "</br>");N = 3;document.write(F(N, a, b, m, n) + "</br>");N = 4;document.write(F(N, a, b, m, n) + "</br>");N = 5;document.write(F(N, a, b, m, n)); // This code is contributed by Ankita saini </script> |
Output:
2 7 20 61
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
