You are given two positive numbers M and N. The task is to print greatest common divisor of M’th and N’th Fibonacci Numbers.
The first few Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
Note that 0 is considered as 0’th Fibonacci Number.
Examples:
Input : M = 3, N = 6 Output : 2 Fib(3) = 2, Fib(6) = 8 GCD of above two numbers is 2 Input : M = 8, N = 12 Output : 3 Fib(8) = 21, Fib(12) = 144 GCD of above two numbers is 3
A Simple Solution is to follow below steps.
1) Find M’th Fibonacci Number.
2) Find N’th Fibonacci Number.
3) Return GCD of two numbers.
A Better Solution is based on below identity
GCD(Fib(M), Fib(N)) = Fib(GCD(M, N)) The above property holds because Fibonacci Numbers follow Divisibility Sequence, i.e., if M divides N, then Fib(M) also divides N. For example, Fib(3) = 2 and every third third Fibonacci Number is even. Source : Wiki
The steps are:
1) Find GCD of M and N. Let GCD be g.
2) Return Fib(g).
Below are implementations of above idea.
C++
// C++ Program to find GCD of Fib(M) and Fib(N)#include <bits/stdc++.h>using namespace std;const int MAX = 1000;// Create an array for memoizationint f[MAX] = { 0 };// Returns n'th Fibonacci number using table f[].// Refer method 6 of below post for details.int fib(int n){ // Base cases if (n == 0) return 0; if (n == 1 || n == 2) return (f[n] = 1); // If fib(n) is already computed if (f[n]) return f[n]; int k = (n & 1) ? (n + 1) / 2 : n / 2; // Applying recursive formula [Note value n&1 is 1 // if n is odd, else 0. f[n] = (n & 1) ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) : (2 * fib(k - 1) + fib(k)) * fib(k); return f[n];}// Function to return gcd of a and bint gcd(int M, int N){ if (M == 0) return N; return gcd(N % M, M);}// Returns GCD of Fib(M) and Fib(N)int findGCDofFibMFibN(int M, int N){ return fib(gcd(M, N));}// Driver codeint main(){ int M = 3, N = 12; cout << findGCDofFibMFibN(M, N); return 0;} |
C
// C Program to find GCD of Fib(M) and Fib(N)#include <stdio.h>const int MAX = 1000;// Returns n'th Fibonacci number using table arr[].// Refer method 6 of below post for details.int fib(int n){ // Create an array for memoization int arr[MAX]; for (int i = 0; i < MAX; i++) arr[i] = 0; // Base cases if (n == 0) return 0; if (n == 1 || n == 2) return (arr[n] = 1); // If fib(n) is already computed if (arr[n]) return arr[n]; int k = (n & 1) ? (n + 1) / 2 : n / 2; // Applying recursive formula [Note value n&1 is 1 // if n is odd, else 0. arr[n] = (n & 1) ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) : (2 * fib(k - 1) + fib(k)) * fib(k); return arr[n];}// Function to return gcd of a and bint gcd(int M, int N){ if (M == 0) return N; return gcd(N % M, M);}// Returns GCD of Fib(M) and Fib(N)int findGCDofFibMFibN(int M, int N){ return fib(gcd(M, N));}// Driver codeint main(){ int M = 3, N = 12; printf("%d", findGCDofFibMFibN(M, N)); return 0;}// This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java Program to find GCD of Fib(M) and Fib(N)class gcdOfFibonacci{ static final int MAX = 1000; static int[] f; gcdOfFibonacci() // Constructor { // Create an array for memoization f = new int[MAX]; } // Returns n'th Fibonacci number using table f[]. // Refer method 6 of below post for details. private static int fib(int n) { // Base cases if (n == 0) return 0; if (n == 1 || n == 2) return (f[n] = 1); // If fib(n) is already computed if (f[n]!=0) return f[n]; int k = ((n & 1)==1)? (n+1)/2 : n/2; // Applying recursive formula [Note value n&1 is 1 // if n is odd, else 0. f[n] = ((n & 1)==1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) : (2*fib(k-1) + fib(k))*fib(k); return f[n]; } // Function to return gcd of a and b private static int gcd(int M, int N) { if (M == 0) return N; return gcd(N%M, M); } // This method returns GCD of Fib(M) and Fib(N) static int findGCDofFibMFibN(int M, int N) { return fib(gcd(M, N)); } // Driver method public static void main(String[] args) { // Returns GCD of Fib(M) and Fib(N) gcdOfFibonacci obj = new gcdOfFibonacci(); int M = 3, N = 12; System.out.println(findGCDofFibMFibN(M, N)); }}// This code is contributed by Pankaj Kumar |
Python3
# Python Program to find# GCD of Fib(M) and Fib(N)MAX = 1000 # Create an array for memoizationf=[0 for i in range(MAX)] # Returns n'th Fibonacci# number using table f[]. # Refer method 6 of below# post for details.def fib(n): # Base cases if (n == 0): return 0 if (n == 1 or n == 2): f[n] = 1 # If fib(n) is already computed if (f[n]): return f[n] k = (n+1)//2 if(n & 1) else n//2 # Applying recursive # formula [Note value n&1 is 1 # if n is odd, else 0. f[n] = (fib(k)*fib(k) + fib(k-1)*fib(k-1)) if(n & 1) else ((2* fib(k-1) + fib(k))*fib(k)) return f[n] # Function to return# gcd of a and bdef gcd(M, N): if (M == 0): return N return gcd(N % M, M) # Returns GCD of# Fib(M) and Fib(N)def findGCDofFibMFibN(M, N): return fib(gcd(M, N)) # Driver codeM = 3N = 12print(findGCDofFibMFibN(M, N))# This code is contributed# by Anant Agarwal. |
C#
// C# Program to find GCD of // Fib(M) and Fib(N)using System;class gcdOfFibonacci { static int MAX = 1000; static int []f; // Constructor gcdOfFibonacci() { // Create an array // for memoization f = new int[MAX]; } // Returns n'th Fibonacci number // using table f[]. Refer method // 6 of below post for details. private static int fib(int n) { // Base cases if (n == 0) return 0; if (n == 1 || n == 2) return (f[n] = 1); // If fib(n) is // already computed if (f[n]!=0) return f[n]; int k = ((n & 1)==1)? (n+1)/2 : n/2; // Applying recursive formula // [Note value n&1 is 1 // if n is odd, else 0. f[n] = ((n & 1) == 1) ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) : (2 * fib(k - 1) + fib(k)) * fib(k); return f[n]; } // Function to return gcd of a and b private static int gcd(int M, int N) { if (M == 0) return N; return gcd(N%M, M); } // This method returns GCD of // Fib(M) and Fib(N) static int findGCDofFibMFibN(int M, int N) { return fib(gcd(M, N)); } // Driver method public static void Main() { // Returns GCD of Fib(M) and Fib(N) new gcdOfFibonacci(); int M = 3, N = 12; Console.Write(findGCDofFibMFibN(M, N)); }}// This code is contributed by nitin mittal. |
PHP
<?php// PHP Program to find// GCD of Fib(M) and Fib(N)$MAX = 1000;// Create an array for memoization$f = array_fill(0, $MAX, 0);// Returns n'th Fibonacci number // using table f[]. Refer method // 6 of below post for details.function fib($n){ global $f; // Base cases if ($n == 0) return 0; if ($n == 1 or $n == 2) $f[$n] = 1; // If fib(n) is already computed if ($f[$n]) return $f[$n]; $k = ($n & 1) ? ($n + 1) / 2 : $n / 2; // Applying recursive formula [Note // value n&1 is 1, if n is odd, else 0. $f[$n] = ($n & 1) ? (fib($k) * fib($k) + fib($k - 1) * fib($k - 1)) : ((2 * fib($k - 1) + fib($k)) * fib($k)); return $f[$n];}// Function to return gcd of a and bfunction gcd($M, $N){ if ($M == 0) return $N; return gcd($N % $M, $M);}// Returns GCD of Fib(M) and Fib(N)function findGCDofFibMFibN($M, $N){ return fib(gcd($M, $N));}// Driver code$M = 3;$N = 12;print(findGCDofFibMFibN($M, $N))// This code is contributed// by mits?> |
Javascript
<script> // JavaScript Program to find GCD of Fib(M) and Fib(N) const MAX = 1000; // Create an array for memoization var f = [...Array(MAX)]; f.fill(0); // Returns n'th Fibonacci number using table f[]. // Refer method 6 of below post for details. function fib(n) { // Base cases if (n == 0) return 0; if (n == 1 || n == 2) return (f[n] = 1); // If fib(n) is already computed if (f[n]) return f[n]; var k = n & 1 ? (n + 1) / 2 : n / 2; // Applying recursive formula [Note value n&1 is 1 // if n is odd, else 0. f[n] = n & 1 ? fib(k) * fib(k) + fib(k - 1) * fib(k - 1) : (2 * fib(k - 1) + fib(k)) * fib(k); return f[n]; } // Function to return gcd of a and b function gcd(M, N) { if (M == 0) return N; return gcd(N % M, M); } // Returns GCD of Fib(M) and Fib(N) function findGCDofFibMFibN(M, N) { return fib(gcd(M, N)); } // Driver code var M = 3, N = 12; document.write(findGCDofFibMFibN(M, N)); // This code is contributed by rdtank. </script> |
Output:
2
This article is contributed by Shubham Agrawal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
