Given four integers A, B, C and N, where A, B, C represents the first three numbers of the geekonacci series, the task is to find the Nth term of the geekonacci series.
The Nth term of the geekonacci series is the sum of its previous three terms in the series i.e., sum of (N – 1)th, (N – 2)th, and (N – 3)th geekonacci numbers.
Examples:
Input: A = 1, B = 3, C = 2, N = 4
Output: 6
Explanation: The geekonacci series is 1, 3, 2, 6, 11, 19, ……
Therefore, the 4th geekonacci number is 6.Input: A = 1, B = 3, C = 2, N = 6
Output: 19
Recursive Approach: The ‘find'
function is implemented using recursion to calculate the Nth term of the geekonacci series. Let’s understand how the recursion works step by step:
- if N==1, then return A.
- if N==2, then return B.
- if N==3, then return C.
- If N > 3, recursively call find(A, B, C, N – 1) +find(A, B, C, N – 2) +find(A, B, C, N – 3).
- Finally, the function returns the sum of the three recursive calls, which represents the Nth term of the geekonacci series.
Below is the implementation of the above approach:
C++
// Fibonacci Series using Recursion #include <iostream> using namespace std; int find( int A, int B, int C, int N) { if (N == 1) return A; else if (N == 2) return B; else if (N == 3) return C; return find(A, B, C, N - 1) + find(A, B, C, N - 2) + find(A, B, C, N - 3); } // Driver code int main() { int A = 1, B = 3, C = 2, N = 4; int result = find(A, B, C, N); cout << result << endl; return 0; } // This code is contributed by Abhishek Kumar |
C
// Fibonacci Series using Recursion #include <stdio.h> int find( int A, int B, int C, int N) { if (N == 1) return A; else if (N == 2) return B; else if (N == 3) return C; return find(A, B, C, N - 1) + find(A, B, C, N - 2) + find(A, B, C, N - 3); } // Driver code int main() { int A = 1, B = 3, C = 2, N = 4; int result = find(A, B, C, N); printf ( "%d\n" , result); return 0; } // This code is contributed by Abhishek Kumar |
Java
// Fibonacci Series using Recursion import java.io.*; class GFG { static int find( int A, int B, int C, int N) { if (N == 1 ) return A; else if (N == 2 ) return B; else if (N == 3 ) return C; return find(A, B, C, N - 1 ) + find(A, B, C, N - 2 ) + find(A, B, C, N - 3 ); } // Driver code public static void main(String args[]) { int A = 1 , B = 3 , C = 2 , N = 4 ; int result = find(A, B, C, N); System.out.println(result); } } // This code is contributed by Abhishek Kumar |
Python3
#Fibonacci Series using Recursion def find(A, B, C, N): if N = = 1 : return A elif N = = 2 : return B elif N = = 3 : return C return find(A, B, C, N - 1 ) + find(A, B, C, N - 2 ) + find(A, B, C, N - 3 ) #Driver code A = 1 B = 3 C = 2 N = 4 result = find(A, B, C, N) print (result) #This code is contributed by Abhishek Kumar |
C#
// Fibonacci Series using Recursion using System; public class Gfg{ static int find( int A, int B, int C, int N) { if (N == 1) return A; else if (N == 2) return B; else if (N == 3) return C; return find(A, B, C, N - 1) + find(A, B, C, N - 2) + find(A, B, C, N - 3); } // Driver code public static void Main( string [] args) { int A = 1, B = 3, C = 2, N = 4; int result = find(A, B, C, N); Console.Write(result); } } |
Javascript
function find(A, B, C, N) { if (N == 1) return A; else if (N == 2) return B; else if (N == 3) return C; return find(A, B, C, N - 1) + find(A, B, C, N - 2) + find(A, B, C, N - 3); } const A = 1, B = 3, C = 2, N = 4; const result = find(A, B, C, N); console.log(result); |
6
Time Complexity: O(3^n)
Auxiliary Space: O(n)
Approach: The given problem can be solved by generating the geekonacci series upto N terms and print the Nth term of the series obtained. Follow the steps below to solve this problem:
- Initialize an array arr[] of size N and initialize arr[0] = A, arr[1] = B, and arr[2] = C.
- Iterate over the range [3, N – 1] and update the value of each every ith element, i.e. arr[i] as (arr[i – 1] + arr[i – 2] + arr[i – 3]) to get the ith term of the geekonacci series.
- After completing the above steps, print the value of arr[N – 1] as the resultant Nth number of the geekonacci series.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to calculate the // N-th Geek-onacci Number int find( int A, int B, int C, int N) { // Stores the geekonacci series int arr[N]; // Store the first three // terms of the series arr[0] = A; arr[1] = B; arr[2] = C; // Iterate over the range [3, N] for ( int i = 3; i < N; i++) { // Update the value of arr[i] // as the sum of previous 3 // terms in the series arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]; } // Return the last element // of arr[] as the N-th term return arr[N - 1]; } // Driver Code int main() { int A = 1, B = 3, C = 2, N = 4; cout<<(find(A, B, C, N)); return 0; } // This code is contributed by mohit kumar 29. |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to calculate the // N-th Geek-onacci Number static int find( int A, int B, int C, int N) { // Stores the geekonacci series int [] arr = new int [N]; // Store the first three // terms of the series arr[ 0 ] = A; arr[ 1 ] = B; arr[ 2 ] = C; // Iterate over the range [3, N] for ( int i = 3 ; i < N; i++) { // Update the value of arr[i] // as the sum of previous 3 // terms in the series arr[i] = arr[i - 1 ] + arr[i - 2 ] + arr[i - 3 ]; } // Return the last element // of arr[] as the N-th term return arr[N - 1 ]; } // Driver Code public static void main(String[] args) { int A = 1 , B = 3 , C = 2 , N = 4 ; System.out.print(find(A, B, C, N)); } } |
Python3
# Python3 program for the above approach # Function to calculate the # N-th Geek-onacci Number def find(A, B, C, N) : # Stores the geekonacci series arr = [ 0 ] * N # Store the first three # terms of the series arr[ 0 ] = A arr[ 1 ] = B arr[ 2 ] = C # Iterate over the range [3, N] for i in range ( 3 , N): # Update the value of arr[i] # as the sum of previous 3 # terms in the series arr[i] = (arr[i - 1 ] + arr[i - 2 ] + arr[i - 3 ]) # Return the last element # of arr[] as the N-th term return arr[N - 1 ] # Driver Code A = 1 B = 3 C = 2 N = 4 print (find(A, B, C, N)) # This code is contributed by sanjoy_62. |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate the // N-th Geek-onacci Number static int find( int A, int B, int C, int N) { // Stores the geekonacci series int [] arr = new int [N]; // Store the first three // terms of the series arr[0] = A; arr[1] = B; arr[2] = C; // Iterate over the range [3, N] for ( int i = 3; i < N; i++) { // Update the value of arr[i] // as the sum of previous 3 // terms in the series arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]; } // Return the last element // of arr[] as the N-th term return arr[N - 1]; } // Driver Code public static void Main( string [] args) { int A = 1, B = 3, C = 2, N = 4; Console.Write(find(A, B, C, N)); } } // This code is contributed by code_hunt. |
Javascript
<script> // Javascript program for the above approach // Function to calculate the // N-th Geek-onacci Number function find(A, B, C, N) { // Stores the geekonacci series let arr = new Array(N).fill(0); // Store the first three // terms of the series arr[0] = A; arr[1] = B; arr[2] = C; // Iterate over the range [3, N] for (let i = 3; i < N; i++) { // Update the value of arr[i] // as the sum of previous 3 // terms in the series arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]; } // Return the last element // of arr[] as the N-th term return arr[N - 1]; } // Driver code let A = 1, B = 3, C = 2, N = 4; document.write(find(A, B, C, N)); </script> |
6
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : O(1) space complexity approach
Use variable instead of array to store previous computations because the current value if depend upon the previous 3 computations , So we just need 3 variable to optimize the space complexity.
Implementations Steps :
- Initialize the last three terms in series prev1 , prev2 , prev3.
- Use a loop to calculate the N-th term of the series (starting from 4).
- For each iteration, calculate the current term as the sum of the previous 3 terms.
- Update the previous 3 terms for the next iteration.
- Return the N-th term of the series.
Implementation :
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the N-th Geek-onacci Number int find( int A, int B, int C, int N) { // Stores the last three terms in the series int prev1 = A, prev2 = B, prev3 = C; int curr; // Iterate over the range [4, N] for ( int i = 4; i <= N; i++) { // Calculate the current term as the sum of previous 3 terms curr = prev1 + prev2 + prev3; // Update the previous terms for the next iteration prev1 = prev2; prev2 = prev3; prev3 = curr; } // Return the N-th term return curr; } // Driver Code int main() { int A = 1, B = 3, C = 2, N = 4; cout << find(A, B, C, N); return 0; } // this code is contributed by bhardwajji |
Java
import java.util.*; public class Main { // Function to calculate the N-th Geek-onacci Number public static int find( int A, int B, int C, int N) { // Stores the last three terms in the series int prev1 = A, prev2 = B, prev3 = C; int curr = 0 ; // Iterate over the range [4, N] for ( int i = 4 ; i <= N; i++) { // Calculate the current term as the sum of previous 3 terms curr = prev1 + prev2 + prev3; // Update the previous terms for the next iteration prev1 = prev2; prev2 = prev3; prev3 = curr; } // Return the N-th term return curr; } // Driver Code public static void main(String[] args) { int A = 1 , B = 3 , C = 2 , N = 4 ; System.out.println(find(A, B, C, N)); } } |
Python3
# Python program for above approach # Function to calculate the N-th Geek-onacci Number def find(A, B, C, N): # Stores the last three terms in the series prev1, prev2, prev3 = A, B, C # Iterate over the range [4, N] for i in range ( 4 , N + 1 ): # Calculate the current term as the sum of previous 3 terms curr = prev1 + prev2 + prev3 # Update the previous terms for the next iteration prev1, prev2, prev3 = prev2, prev3, curr # Return the N-th term return curr # Driver Code if __name__ = = '__main__' : A, B, C, N = 1 , 3 , 2 , 4 print (find(A, B, C, N)) |
C#
using System; class Program { static int Find( int A, int B, int C, int N) { // Stores the last three terms // in the series int prev1 = A, prev2 = B, prev3 = C; int curr = 0; // Iterate over the range [4, N] for ( int i = 4; i <= N; i++) { // Calculate the current term as // the sum of previous 3 terms curr = prev1 + prev2 + prev3; // Update the previous terms for // the next iteration prev1 = prev2; prev2 = prev3; prev3 = curr; } // Return the N-th term return curr; } // Driver Code static void Main( string [] args) { int A = 1, B = 3, C = 2, N = 4; Console.WriteLine(Find(A, B, C, N)); } } |
Javascript
// Function to calculate the N-th Geek-onacci Number function find(A, B, C, N) { // Stores the last three terms in the series let prev1 = A, prev2 = B, prev3 = C; let curr = 0; // Iterate over the range [4, N] for (let i = 4; i <= N; i++) { // Calculate the current term as the sum of previous 3 terms curr = prev1 + prev2 + prev3; // Update the previous terms for the next iteration prev1 = prev2; prev2 = prev3; prev3 = curr; } // Return the N-th term return curr; } // Driver Code const A = 1, B = 3, C = 2, N = 4; console.log(find(A, B, C, N)); |
6
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!