Given five integers i, Fi, j, Fj and N. Where Fi and Fj are the ith and jth term of a sequence which follows the Fibonacci recurrence i.e. FN = FN – 1 + FN – 2. The task is to find the Nth term of the original sequence.
Examples:
Input: i = 3, F3 = 5, j = -1, F-1 = 4, N = 5
Output: 12
Fibonacci sequence can be reconstructed using known values:
…, F-1 = 4, F0 = -1, F1 = 3, F2 = 2, F3 = 5, F4 = 7, F5 = 12, …
Input: i = 0, F0 = 1, j = 1, F1 = 4, N = -2
Output: -2
Approach: Note that, if the two consecutive terms of the Fibonacci sequence are known then the Nth term can easily be determined. Assuming i < j, as per Fibonacci condition:
Fi+1 = 1*Fi+1 + 0*Fi
Fi+2 = 1*Fi+1 + 1*Fi
Fi+3 = Fi+2 + Fi+1 = 2*Fi+1 + 1*Fi
Fi+4 = Fi+3 + Fi+2 = 3*Fi+1 + 2*Fi
Fi+5 = Fi+4 + Fi+3 = 5*Fi+1 + 3*Fi
.. .. ..
and so on
Note that, the coefficients of Fi+1 and Fi in the above set of equations are nothing but the terms of Standard Fibonacci Sequence.
So, considering the Standard Fibonacci sequence i.e. f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, … ; we can generalize, the above set of equations (for k > 0) as:
Fi+k = fk*Fi+1 + fk-1*Fi …(1)
Now consider,
k = j-i …(2)
Now, substituting eq.(2) in eq.(1), we get:
Fj = fj-i*Fi+1 + fj-i-1*Fi
Hence, we can calculate Fi+1 from known values of Fi and Fj. Now that we know two consecutive terms of sequence F, we can easily reconstruct F and determine the value of FN.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;// Function to calculate kth Fibonacci number// in the standard Fibonacci sequenceint fibonacci(int k){ int a = 0, b = 1, c = 0; if( k == 0) return a; if (k == 1) return b; for(int i = 2; i < k + 1; i++) { c = a + b; a = b; b = c; } return c;}// Function to determine the value of F(n)int determineFn(int i, int Fi, int j, int Fj, int n){ if (j < i) { swap(i, j); swap(Fi, Fj); } // Find the value of F(i + 1) // from F(i) and F(j) int Fi1 = (Fj - fibonacci(j - i - 1) * Fi) / fibonacci(j - i); // When n is equal to i int Fn = 0; if (n == i) Fn = Fi; // When n is greater than i else if (n > i) { int b = Fi; Fn = Fi1; n = n - 1; while (n != i) { n = n - 1; int a = b; b = Fn; Fn = a + b; } } // When n is smaller than i else { int a = Fi; int b = Fi1; while (n != i) { n = n + 1; Fn = b - a; b = a; a = Fn; } } return Fn;}// Driver codeint main(){ int i = 3; int Fi = 5; int j = -1; int Fj = 4; int n = 5; cout << (determineFn(i, Fi, j, Fj, n));}// This code is contributed by Mohit Kumar |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function to calculate kth Fibonacci number // in the standard Fibonacci sequence static int fibonacci(int k) { int a = 0, b = 1, c = 0; if (k == 0) return a; if (k == 1) return b; for (int i = 2; i < k + 1; i++) { c = a + b; a = b; b = c; } return c; } // Function to determine the value of F(n) static int determineFn(int i, int Fi, int j, int Fj, int n) { if (j < i) { // Swap i, j i = i + j; j = i - j; i = i - j; // swap Fi, Fj Fi = Fi + Fj; Fj = Fi - Fj; Fi = Fi - Fj; } // Find the value of F(i + 1) // from F(i) and F(j) int Fi1 = (Fj - fibonacci(j - i - 1) * Fi) / fibonacci(j - i); // When n is equal to i int Fn = 0; if (n == i) Fn = Fi; // When n is greater than i else if (n > i) { int b = Fi; Fn = Fi1; n = n - 1; while (n != i) { n = n - 1; int a = b; b = Fn; Fn = a + b; } } // When n is smaller than i else { int a = Fi; int b = Fi1; while (n != i) { n = n + 1; Fn = b - a; b = a; a = Fn; } } return Fn; } // Driver Code public static void main(String[] args) { int i = 3; int Fi = 5; int j = -1; int Fj = 4; int n = 5; System.out.println(determineFn(i, Fi, j, Fj, n)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the approach# Function to calculate kth Fibonacci number # in the standard Fibonacci sequencedef fibonacci(k): a = 0 b = 1 if k == 0: return a if k == 1: return b for i in range(2, k + 1): c = a + b a = b b = c return c# Function to determine# the value of F(n)def determineFn(i, Fi, j, Fj, n): if j<i: i, j = j, i Fi, Fj = Fj, Fi # Find the value of F(i + 1) # from F(i) and F(j) Fi1 = (Fj - fibonacci(j-i-1)*Fi)\ //fibonacci(j-i) # When n is equal to i if n == i: Fn = Fi # When n is greater than i elif n>i: b = Fi Fn = Fi1 n = n - 1 while n != i: n = n - 1 a = b b = Fn Fn = a + b # When n is smaller than i else: a = Fi b = Fi1 while n != i: n = n + 1 Fn = b - a b = a a = Fn return Fn# Driver codeif __name__ == '__main__': i = 3 Fi = 5 j = -1 Fj = 4 n = 5 print(determineFn(i, Fi, j, Fj, n)) |
C#
// C# implementation of the approachusing System;class GFG{ // Function to calculate kth Fibonacci number // in the standard Fibonacci sequence static int fibonacci(int k) { int a = 0, b = 1, c = 0; if (k == 0) return a; if (k == 1) return b; for (int i = 2; i < k + 1; i++) { c = a + b; a = b; b = c; } return c; } // Function to determine the value of F(n) static int determineFn(int i, int Fi, int j, int Fj, int n) { if (j < i) { // Swap i, j i = i + j; j = i - j; i = i - j; // swap Fi, Fj Fi = Fi + Fj; Fj = Fi - Fj; Fi = Fi - Fj; } // Find the value of F(i + 1) // from F(i) and F(j) int Fi1 = (Fj - fibonacci(j - i - 1) * Fi) / fibonacci(j - i); // When n is equal to i int Fn = 0; if (n == i) Fn = Fi; // When n is greater than i else if (n > i) { int b = Fi; Fn = Fi1; n = n - 1; while (n != i) { n = n - 1; int a = b; b = Fn; Fn = a + b; } } // When n is smaller than i else { int a = Fi; int b = Fi1; while (n != i) { n = n + 1; Fn = b - a; b = a; a = Fn; } } return Fn; } // Driver Code public static void Main(String[] args) { int i = 3; int Fi = 5; int j = -1; int Fj = 4; int n = 5; Console.WriteLine(determineFn(i, Fi, j, Fj, n)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach// Function to calculate kth Fibonacci number// in the standard Fibonacci sequencefunction fibonacci(k){ let a = 0, b = 1, c = 0; if( k == 0) return a; if (k == 1) return b; for(let i = 2; i < k + 1; i++) { c = a + b; a = b; b = c; } return c;}// Function to determine the value of F(n)function determineFn(i, Fi, j, Fj, n){ if (j < i) { // Swap i, j i = i + j; j = i - j; i = i - j; // swap Fi, Fj Fi = Fi + Fj; Fj = Fi - Fj; Fi = Fi - Fj; } // Find the value of F(i + 1) // from F(i) and F(j) let Fi1 = parseInt((Fj - fibonacci(j - i - 1) * Fi) / fibonacci(j - i)); // When n is equal to i let Fn = 0; if (n == i) Fn = Fi; // When n is greater than i else if (n > i) { let b = Fi; Fn = Fi1; n = n - 1; while (n != i) { n = n - 1; let a = b; b = Fn; Fn = a + b; } } // When n is smaller than i else { let a = Fi; let b = Fi1; while (n != i) { n = n + 1; Fn = b - a; b = a; a = Fn; } } return Fn;}// Driver code let i = 3; let Fi = 5; let j = -1; let Fj = 4; let n = 5; document.write(determineFn(i, Fi, j, Fj, n));</script> |
12
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!
