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 numberint 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 approachint 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 codeint 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 numberdef 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 approachdef 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 codeindices = [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 numberfunction getFib(n){ if (n <= 1) return n; return getFib(n-1) + getFib(n-2);}// Function to computr gcdfunction 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 approachfunction 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 codelet indices = [ 3, 6, 9 ];let n = indices.length;document.write(findGCD(indices, n)); |
Output
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 numberint 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 Indicesint 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 codeint 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 Indicesimport java.io.*;// Function to return n'th// Fibonacci numberpublic 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 Indicesstatic 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 Indicesdef 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 Indicesusing System;// Function to return n'th// Fibonacci numberclass 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 Indicesstatic 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 codepublic 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 numberfunction 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 Indicesfunction 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?> |
Output
2
Time Complexity: O(nlogn)
Auxiliary Space: O(n)
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!
