Given three integers X, Y and N, the task is to find the Nth term of the series f[i] = f[i – 1] – f[i – 2], i > 1 where f[0] = X and f[1] = Y.
Examples:
Input: X = 2, Y = 3, N = 3
Output: -2
The series will be 2 3 1 -2 -3 -1 2 and f[3] = -2
Input: X = 3, Y = 7, N = 8
Output: 4
Approach: An important observation here is that there will be atmost 6 distinct terms, before the sequence starts repeating itself. So, find the first 6 terms of the series and then the Nth term would be same as the (N % 6)th term.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the Nth term// of the given seriesint findNthTerm(int x, int y, int n){ int f[6]; // First and second term of the series f[0] = x; f[1] = y; // Find first 6 terms for (int i = 2; i <= 5; i++) f[i] = f[i - 1] - f[i - 2]; // Return the Nth term return f[n % 6];}// Driver codeint main(){ int x = 2, y = 3, n = 3; cout << findNthTerm(x, y, n); return 0;} |
Java
// Java implementation of the approachimport java.io.*; class GFG { // Function to find the nth term of series static int findNthTerm(int x, int y, int n) { int[] f = new int[6]; f[0] = x; f[1] = y; // Loop to add numbers for (int i = 2; i <= 5; i++) f[i] = f[i - 1] - f[i - 2]; return f[n % 6]; } // Driver code public static void main(String args[]) { int x = 2, y = 3, n = 3; System.out.println(findNthTerm(x, y, n)); } } // This code is contributed by mohit kumar 29 |
Python3
# Python3 implementation of the approach # Function to return the Nth term # of the given series def findNthTerm(x, y, n): f = [0] * 6 # First and second term of # the series f[0] = x f[1] = y # Find first 6 terms for i in range(2, 6): f[i] = f[i - 1] - f[i - 2] # Return the Nth term return f[n % 6] # Driver code if __name__ == "__main__": x, y, n = 2, 3, 3 print(findNthTerm(x, y, n))# This code is contributed by# Rituraj Jain |
C#
// C# implementation of the approach using System;class GFG { // Function to find the nth term of series static int findNthTerm(int x, int y, int n) { int[] f = new int[6]; f[0] = x; f[1] = y; // Loop to add numbers for (int i = 2; i <= 5; i++) f[i] = f[i - 1] - f[i - 2]; return f[n % 6]; } // Driver code public static void Main() { int x = 2, y = 3, n = 3; Console.WriteLine(findNthTerm(x, y, n)); } } // This code is contributed by Ryuga |
Javascript
<script>// JavaScript implementation of the approach // Function to return the Nth term // of the given series function findNthTerm(x, y, n) { let f = new Array(6); // First and second term of the series f[0] = x; f[1] = y; // Find first 6 terms for (let i = 2; i <= 5; i++) f[i] = f[i - 1] - f[i - 2]; // Return the Nth term return f[n % 6]; } // Driver code let x = 2, y = 3, n = 3; document.write(findNthTerm(x, y, n)); // This code is contributed by Surbhi Tyagi</script> |
PHP
<?php//PHP implementation of the approach// Function to find the nth term of series function findNthTerm($x, $y, $n){ $f = array(6); $f[0] = $x; $f[1] = $y; // Loop to add numbers for ($i = 2; $i <= 5; $i++) $f[$i] = $f[$i - 1] - $f[$i - 2]; return $f[$n % 6]; } // Driver code $x = 2; $y = 3; $n = 3; echo(findNthTerm($x, $y, $n)); // This code is contributed by Code_Mech.?> |
Output
-2
Time Complexity: O(1) Since no loop is used the algorithm takes up constant time to perform the operations
Auxiliary Space: O(1) Since no extra array is used so the space taken by the algorithm is constant
Method 2 (Space Optimized Method 2) :
We can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next sequence number in the series.
Steps :
1.Define a function "fib" that takes three integer parameters: x, y, and n.
2.Initialize variables a and b to x and y, respectively, and declare a variable c.
3.If n is equal to zero, return the value of a.
4.For i = 2 to n, calculate the next term of the Fibonacci series using the space-optimized method (c = b - a, a = b, b = c).
5.Return the value of b.
6.In the main function, initialize variables x, y, and n, and call the "fib" function with these values.
7.Print the result.
C++
// Fibonacci Series using Space Optimized Method#include <bits/stdc++.h>using namespace std;// Function to generate Fibonacci series using space-optimized methodint fib(int x, int y, int n){ // Initialize variables a and b to x and y, respectively, and declare a variable c and loop variable i. int a = x, b = y, c, i; // If n is equal to zero, return the value of a. if (n == 0) return a; // For i = 2 to n, calculate the next term of the Fibonacci series using the space-optimized method (c = b - a, a = b, b = c). for (i = 2; i <= n; i++) { c = b - a; a = b; b = c; } // Return the value of b, which represents the nth term of the Fibonacci series. return b;}// Driver codeint main(){ // Initialize variables x, y, and n. int x = 2, y = 3; int n = 3; // Call the "fib" function with initial values for x, y, and n and print the result. cout << fib(2, 3, 3); return 0;} |
Java
// Fibonacci Series using Space Optimized Methodimport java.io.*;class GFG { // Function to generate Fibonacci series using // space-optimized method public static int fib(int x, int y, int n) { // Initialize variables a and b to x and y, // respectively, and declare a variable c and loop // variable i. int a = x, b = y, c, i; // If n is equal to zero, return the value of a. if (n == 0) return a; // For i = 2 to n, calculate the next term of the // Fibonacci series using the space-optimized method // (c = b - a, a = b, b = c). for (i = 2; i <= n; i++) { c = b - a; a = b; b = c; } // Return the value of b, which represents the nth // term of the Fibonacci series. return b; } // Driver code public static void main(String[] args) { // Initialize variables x, y, and n. int x = 2, y = 3; int n = 3; // Call the "fib" function with initial values for // x, y, and n and print the result. System.out.println(fib(2, 3, 3)); }}// This code is contributed by Taranpreet Singh |
Python3
# Fibonacci Series using Space Optimized Method# Function to generate Fibonacci series using space-optimized methoddef fib(x, y, n): # Initialize variables a and b to x and y, # respectively, and declare a variable c and loop variable i. a, b = x, y c = 0 # If n is equal to zero, return the value of a. if n == 0: return a # For i = 2 to n, calculate the next term of the # Fibonacci series using the space-optimized # method (c = b - a, a = b, b = c). for i in range(2, n + 1): c = b - a a = b b = c # Return the value of b, which # represents the nth term of the Fibonacci series. return b# Driver codedef main(): # Initialize variables x, y, and n. x = 2 y = 3 n = 3 # Call the "fib" function with initial values for x, y, and n and print the result. print(fib(x, y, n))if __name__ == "__main__": main()# This code is contributed by Dwaipayan Bandyopadhyay |
Javascript
// Nikunj Sonigara// Function to generate Fibonacci series using space-optimized methodfunction fib(x, y, n) { // Initialize variables a and b to x and y, respectively, and declare a variable c. let a = x; let b = y; let c; // If n is equal to zero, return the value of a. if (n === 0) { return a; } // For i = 2 to n, calculate the next term of the Fibonacci // series using the space-optimized method (c = b - a, a = b, b = c). for (let i = 2; i <= n; i++) { c = b - a; a = b; b = c; } // Return the value of b, which represents the nth term of the Fibonacci series. return b;}// Driver codefunction main() { // Initialize variables x, y, and n. const x = 2; const y = 3; const n = 3; // Call the "fib" function with initial values for x, y, and n and print the result. console.log(fib(2, 3, 3));}// Call the "main" function to start the program.main(); |
Output
-2
Time Complexity: O(n)
Auxiliary Space: O(1)
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!
