Given a positive integer N, the task is to find the Nth term in the series 0, 1, 1, 2, 5, 29, 841…
Examples:
Input: N = 6
Output: 29
Explanation: The 6th term of the given series is 29.Input: N = 1
Output: 1Input: N = 8
Output: 750797
Approach: The given problem is a basic maths-based problem where the Ai = Ai-12 + Ai-22. Therefore, create variables a = 0 and b = 1. Iterate using the variable i in the range [2, N], and for each i, calculate the ith term and update the value of a and b to i – 1th and i – 2th term respectively.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find N-th term// of the given seriesint getNthTerm(int N){ if (N < 3) return N - 1; // Initialize Variables repre- // senting 1st and 2nd term long int a = 0, b = 1; // Loop to iterate through the // range [3, N] using variable i for (int i = 3; i <= N; i++) { // pow((i - 2)th term, 2) + // pow((i - 1)th term, 2) long int c = a * a + b * b; // Update a and b a = b; b = c; } // Return Answer return b;}// Driver Codeint main(){ int N = 8; cout << getNthTerm(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find N-th term // of the given series static int getNthTerm(int N) { if (N < 3) return N - 1; // Initialize Variables repre- // senting 1st and 2nd term int a = 0, b = 1; // Loop to iterate through the // range [3, N] using variable i for (int i = 3; i <= N; i++) { // Math.pow((i - 2)th term, 2) + // Math.pow((i - 1)th term, 2) int c = a * a + b * b; // Update a and b a = b; b = c; } // Return Answer return b; } // Driver Code public static void main(String[] args) { int N = 8; System.out.print(getNthTerm(N)); }}// This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach# Function to find N-th term# of the given seriesdef getNthTerm(N): if (N < 3): return N - 1 # Initialize Variables repre- # senting 1st and 2nd term a = 0 b = 1 # Loop to iterate through the # range [3, N] using variable i for i in range(3, N + 1): # pow((i - 2)th term, 2) + # pow((i - 1)th term, 2) c = a * a + b * b # Update a and b a = b b = c # Return Answer return b# Driver CodeN = 8print(getNthTerm(N))# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;class GFG{ // Function to find N-th term// of the given seriesstatic int getNthTerm(int N){ if (N < 3) return N - 1; // Initialize Variables repre- // senting 1st and 2nd term long a = 0, b = 1; // Loop to iterate through the // range [3, N] using variable i for (int i = 3; i <= N; i++) { // pow((i - 2)th term, 2) + // pow((i - 1)th term, 2) long c = a * a + b * b; // Update a and b a = b; b = c; } // Return Answer return (int)b;}// Driver Codepublic static void Main(){ int N = 8; Console.Write(getNthTerm(N));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find N-th term // of the given series function getNthTerm(N) { if (N < 3) return N - 1; // Initialize Variables repre- // senting 1st and 2nd term let a = 0, b = 1; // Loop to iterate through the // range [3, N] using variable i for (let i = 3; i <= N; i++) { // pow((i - 2)th term, 2) + // pow((i - 1)th term, 2) let c = a * a + b * b; // Update a and b a = b; b = c; } // Return Answer return b; } // Driver Code let N = 8; document.write(getNthTerm(N));// This code is contributed by Potta Lokesh</script> |
Output
750797
Time complexity: O(N)
Auxiliary space: O(1)
Share your thoughts in the comments
