Find the Nth term of the series where each term f[i] = f[i – 1] – f[i – 2]

0 0 7 minutes read

Given three integers X, Y and N, the task is to find the N^th 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 N^th 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 series
int 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 code
int main()
{
    int x = 2, y = 3, n = 3;
    cout << findNthTerm(x, y, n);
 
    return 0;
}

Java

// Java implementation of the approach
import 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 method
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
int 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 Method
import 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 method
def 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 code
def 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 method
function 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 code
function 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 zambiatek!