Find the GCD of N Fibonacci Numbers with given Indices
Given indices of N Fibonacci numbers. The task is to find the GCD of the Fibonacci numbers present at the given indices.
The first few Fibonacci numbers are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…
Note: The indices start from zero. That is, 0th Fibonacci number = 0.
Examples:
Input: Indices = {2, 3, 4, 5}
Output: GCD of the fibonacci numbers = 1
Input: Indices = {3, 6, 9}
Output: GCD of the fibonacci numbers = 2
Brute Force Approach:
- Initialize an array to store the Fibonacci numbers.
- Calculate the maximum index in the given list of indices.
- Calculate all the Fibonacci numbers up to the maximum index using a loop.
- Extract the Fibonacci numbers at the given indices from the array.
- Compute the GCD of the extracted Fibonacci numbers using a loop and the Euclidean algorithm.
- Return the GCD as the result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to compute the nth Fibonacci number int getFib( int n) { if (n <= 1) return n; return getFib(n-1) + getFib(n-2); } // Function to find the GCD of Fibonacci numbers // at given indices using brute force approach int findGCD( int indices[], int n) { int maxIndex = *max_element(indices, indices+n); vector< int > fib(maxIndex+1); // Compute all Fibonacci numbers up to maxIndex for ( int i = 0; i <= maxIndex; i++) fib[i] = getFib(i); // Compute the GCD of Fibonacci numbers at given indices int gcd = fib[indices[0]]; for ( int i = 1; i < n; i++) gcd = __gcd(gcd, fib[indices[i]]); return gcd; } // Driver code int main() { int indices[] = { 3, 6, 9 }; int n = sizeof (indices)/ sizeof (indices[0]); cout << findGCD(indices, n) << endl; return 0; } |
Java
import java.util.Arrays; import java.util.Vector; public class GFG { // Function to compute the nth Fibonacci number public static int getFib( int n) { if (n <= 1 ) return n; return getFib(n- 1 ) + getFib(n- 2 ); } // Function to find the GCD of Fibonacci numbers // at given indices using brute force approach public static int findGCD( int [] indices, int n) { int maxIndex = Arrays.stream(indices).max().getAsInt(); Vector<Integer> fib = new Vector<Integer>(maxIndex+ 1 ); // Compute all Fibonacci numbers up to maxIndex for ( int i = 0 ; i <= maxIndex; i++) fib.add(getFib(i)); // Compute the GCD of Fibonacci numbers at given indices int gcd = fib.get(indices[ 0 ]); for ( int i = 1 ; i < n; i++) gcd = gcd(gcd, fib.get(indices[i])); return gcd; } // Function to compute the GCD of two numbers public static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Driver code public static void main(String[] args) { int [] indices = { 3 , 6 , 9 }; int n = indices.length; System.out.println(findGCD(indices, n)); } } |
Python3
import math # Function to compute the nth Fibonacci number def get_fib(n): if n < = 1 : return n return get_fib(n - 1 ) + get_fib(n - 2 ) # Function to find the GCD of Fibonacci numbers # at given indices using brute force approach def find_gcd(indices): max_index = max (indices) fib = [ 0 ] * (max_index + 1 ) # Compute all Fibonacci numbers up to max_index for i in range (max_index + 1 ): fib[i] = get_fib(i) # Compute the GCD of Fibonacci numbers at given indices gcd = fib[indices[ 0 ]] for i in range ( 1 , len (indices)): gcd = math.gcd(gcd, fib[indices[i]]) return gcd # Driver code indices = [ 3 , 6 , 9 ] print (find_gcd(indices)) |
C#
using System; using System.Collections.Generic; public class GFG { // Function to compute the nth Fibonacci number public static int GetFib( int n) { if (n <= 1) return n; return GetFib(n - 1) + GetFib(n - 2); } // Function to find the GCD of Fibonacci numbers // at given indices using the brute force approach public static int FindGCD( int [] indices) { int maxIndex = indices[0]; for ( int i = 1; i < indices.Length; i++) { if (indices[i] > maxIndex) maxIndex = indices[i]; } // Compute all Fibonacci numbers up to maxIndex List< int > fib = new List< int >(); for ( int i = 0; i <= maxIndex; i++) fib.Add(GetFib(i)); // Compute the GCD of Fibonacci numbers at given indices int gcd = fib[indices[0]]; for ( int i = 1; i < indices.Length; i++) gcd = GCD(gcd, fib[indices[i]]); return gcd; } // Function to compute the Greatest Common Divisor (GCD) of two numbers public static int GCD( int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // Driver code public static void Main( string [] args) { int [] indices = { 3, 6, 9 }; Console.WriteLine(FindGCD(indices)); } } |
Javascript
// Function to compute the nth Fibonacci number function getFib(n) { if (n <= 1) return n; return getFib(n-1) + getFib(n-2); } // Function to computr gcd function GCD(a, b) { if (b == 0) return a; return GCD(b, a % b); } // Function to find the GCD of Fibonacci numbers // at given indices using brute force approach function findGCD(indices, n) { let maxIndex = Math.max(...indices); let fib = new Array(maxIndex+1); // Compute all Fibonacci numbers up to maxIndex for (let i = 0; i <= maxIndex; i++) fib[i] = getFib(i); // Compute the GCD of Fibonacci numbers at given indices let gcd = fib[indices[0]]; for (let i = 1; i < n; i++) gcd = GCD(gcd, fib[indices[i]]); return gcd; } // Driver code let indices = [ 3, 6, 9 ]; let n = indices.length; document.write(findGCD(indices, n)); |
2
Time Complexity: O(k * n), where k is the number of indices and n is the maximum index in the given array.
Space Complexity: O(maxIndex), where maxIndex is the maximum index in the given array of indices.
Efficient Approach: An efficient approach is to use the property:
GCD(Fib(M), Fib(N)) = Fib(GCD(M, N))
The idea is to calculate the GCD of all the indices and then find the Fibonacci number at the index gcd_1( where gcd_1 is the GCD of the given indices).
Below is the implementation of the above approach:
C++
// C++ program to Find the GCD of N Fibonacci // Numbers with given Indices #include <bits/stdc++.h> using namespace std; // Function to return n'th // Fibonacci number int getFib( int n) { /* Declare an array to store Fibonacci numbers. */ int f[n + 2]; // 1 extra to handle case, n = 0 int i; // 0th and 1st number of the series // are 0 and 1 f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { // Add the previous 2 numbers in the series // and store it f[i] = f[i - 1] + f[i - 2]; } return f[n]; } // Function to Find the GCD of N Fibonacci // Numbers with given Indices int find( int arr[], int n) { int gcd_1 = 0; // find the gcd of the indices for ( int i = 0; i < n; i++) { gcd_1 = __gcd(gcd_1, arr[i]); } // find the fibonacci number at // index gcd_1 return getFib(gcd_1); } // Driver code int main() { int indices[] = { 3, 6, 9 }; int N = sizeof (indices) / sizeof ( int ); cout << find(indices, N); return 0; } |
Java
// Java program to Find the GCD of N Fibonacci // Numbers with given Indices import java.io.*; // Function to return n'th // Fibonacci number public class GFG { // Recursive function to return gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0 ) return b; if (b == 0 ) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } static int getFib( int n) { /* Declare an array to store Fibonacci numbers. */ int f[] = new int [n + 2 ]; // 1 extra to handle case, n = 0 int i; // 0th and 1st number of the series // are 0 and 1 f[ 0 ] = 0 ; f[ 1 ] = 1 ; for (i = 2 ; i <= n; i++) { // Add the previous 2 numbers in the series // and store it f[i] = f[i - 1 ] + f[i - 2 ]; } return f[n]; } // Function to Find the GCD of N Fibonacci // Numbers with given Indices static int find( int arr[], int n) { int gcd_1 = 0 ; // find the gcd of the indices for ( int i = 0 ; i < n; i++) { gcd_1 = __gcd(gcd_1, arr[i]); } // find the fibonacci number at // index gcd_1 return getFib(gcd_1); } // Driver code public static void main (String[] args) { int indices[] = { 3 , 6 , 9 }; int N = indices.length; System.out.println( find(indices, N)); } } |
Python 3
# Python program to Find the # GCD of N Fibonacci Numbers # with given Indices from math import * # Function to return n'th # Fibonacci number def getFib(n) : # Declare an array to store # Fibonacci numbers. f = [ 0 ] * (n + 2 ) # 1 extra to handle case, n = 0 # 0th and 1st number of the # series are 0 and 1 f[ 0 ], f[ 1 ] = 0 , 1 # Add the previous 2 numbers # in the series and store it for i in range ( 2 , n + 1 ) : f[i] = f[i - 1 ] + f[i - 2 ] return f[n] # Function to Find the GCD of N Fibonacci # Numbers with given Indices def find(arr, n) : gcd_1 = 0 # find the gcd of the indices for i in range (n) : gcd_1 = gcd(gcd_1, arr[i]) # find the fibonacci number # at index gcd_1 return getFib(gcd_1) # Driver code if __name__ = = "__main__" : indices = [ 3 , 6 , 9 ] N = len (indices) print (find(indices, N)) # This code is contributed by ANKITRAI1 |
C#
// C# program to Find the GCD // of N Fibonacci Numbers with // given Indices using System; // Function to return n'th // Fibonacci number class GFG { // Recursive function to // return gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } static int getFib( int n) { /* Declare an array to store Fibonacci numbers. */ int []f = new int [n + 2]; // 1 extra to handle case, n = 0 int i; // 0th and 1st number of // the series are 0 and 1 f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { // Add the previous 2 numbers // in the series and store it f[i] = f[i - 1] + f[i - 2]; } return f[n]; } // Function to Find the GCD // of N Fibonacci Numbers // with given Indices static int find( int []arr, int n) { int gcd_1 = 0; // find the gcd of the indices for ( int i = 0; i < n; i++) { gcd_1 = __gcd(gcd_1, arr[i]); } // find the fibonacci number // at index gcd_1 return getFib(gcd_1); } // Driver code public static void Main () { int []indices = { 3, 6, 9 }; int N = indices.Length; Console.WriteLine(find(indices, N)); } } // This code is contributed // by Shashank |
Javascript
<script> // javascript program to // Find the GCD of N Fibonacci // Numbers with given Indices // Function to return n'th // Fibonacci number // Recursive function to return gcd of a and b function __gcd(a , b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } function getFib(n) { /* Declare an array to store Fibonacci numbers. */ var f = Array(n + 2).fill(0); // 1 extra to handle case, n = 0 var i; // 0th and 1st number of the series // are 0 and 1 f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { // Add the previous 2 numbers in the series // and store it f[i] = f[i - 1] + f[i - 2]; } return f[n]; } // Function to Find the GCD of N Fibonacci // Numbers with given Indices function find(arr , n) { var gcd_1 = 0; // find the gcd of the indices for (i = 0; i < n; i++) { gcd_1 = __gcd(gcd_1, arr[i]); } // find the fibonacci number at // index gcd_1 return getFib(gcd_1); } // Driver code var indices = [ 3, 6, 9 ]; var N = indices.length; document.write(find(indices, N)); // This code contributed by gauravrajput1 </script> |
PHP
<?php // PHP program to Find the GCD of // N Fibonacci Numbers with given // Indices // Function to return n'th // Fibonacci number function gcd( $a , $b ) { return $b ? gcd( $b , $a % $b ) : $a ; } function getFib( $n ) { /* Declare an array to store Fibonacci numbers. */ // 1 extra to handle case, n = 0 $f = array_fill (0, ( $n + 2), NULL); // 0th and 1st number of the // series are 0 and 1 $f [0] = 0; $f [1] = 1; for ( $i = 2; $i <= $n ; $i ++) { // Add the previous 2 numbers // in the series and store it $f [ $i ] = $f [ $i - 1] + $f [ $i - 2]; } return $f [ $n ]; } // Function to Find the GCD of N Fibonacci // Numbers with given Indices function find(& $arr , $n ) { $gcd_1 = 0; // find the gcd of the indices for ( $i = 0; $i < $n ; $i ++) { $gcd_1 = gcd( $gcd_1 , $arr [ $i ]); } // find the fibonacci number // at index gcd_1 return getFib( $gcd_1 ); } // Driver code $indices = array (3, 6, 9 ); $N = sizeof( $indices ); echo find( $indices , $N ); // This code is contributed // by ChitraNayal ?> |
2
Time Complexity: O(nlogn)
Auxiliary Space: O(n)