Given two numbers M and N, the task is to check if the M-th and N-th Fibonacci numbers perfectly divide each other or not.
Examples:
Input: M = 3, N = 6
Output: Yes
F(3) = 2, F(6) = 8 and F(6) % F(3) = 0
Input: M = 2, N = 9
Output: Yes
A naive approach will be to find the N-th and M-th Fibonacci numbers and check if they are perfectly divisible or not.
An efficient approach is to use the Fibonacci property to determine the result. If m perfectly divides n, then Fm also perfectly divides Fn, else it does not.
Exception: When N is 2, it is always possible as Fibo2 is 1, which divides every other Fibonacci number.
Below is the implementation of the above approach:
C++
// C++ program to check if // M-th fibonacci divides N-th fibonacci#include <bits/stdc++.h>using namespace std;void check(int n, int m){ // exceptional case for F(2) if (n == 2 || m == 2 || n % m == 0) { cout << "Yes" << endl; } // if none of the above cases, // hence not divisible else { cout << "No" << endl; }}// Driver Codeint main(){ int m = 3, n = 9; check(n, m); return 0;} |
Java
// Java program to check// if M-th fibonacci // divides N-th fibonacciimport java.io.*;class GFG {static void check(int n, int m){ // exceptional case for F(2) if (n == 2 || m == 2 || n % m == 0) { System.out.println( "Yes"); } // if none of the above cases, // hence not divisible else { System.out.println( "No"); }}// Driver Codepublic static void main (String[] args) { int m = 3, n = 9; check(n, m);}}// This code is contributed// by anuj_67. |
Python 3
# Python 3 program to # check if M-th fibonacci # divides N-th fibonaccidef check(n, m): # exceptional case for F(2) if (n == 2 or m == 2 or n % m == 0) : print( "Yes" ) # if none of the above # cases, hence not divisible else : print( "No" )# Driver Codem = 3n = 9check(n, m)# This code is contributed# by Smitha |
C#
// C# program to check// if M-th fibonacci // divides N-th fibonacciusing System;class GFG {static void check(int n, int m){ // exceptional case for F(2) if (n == 2 || m == 2 || n % m == 0) { Console.WriteLine( "Yes"); } // if none of the above cases, // hence not divisible else { Console.WriteLine( "No"); }}// Driver Codepublic static void Main () { int m = 3, n = 9; check(n, m);}}// This code is contributed// by anuj_67. |
PHP
<?php// PHP program to check // if M-th fibonacci // divides N-th fibonaccifunction check($n, $m){ // exceptional case for F(2) if ($n == 2 || $m == 2 || $n % $m == 0) { echo "Yes" , "\n"; } // if none of the above cases, // hence not divisible else { echo "No" ," \n"; }}// Driver Code$m = 3; $n = 9;check($n, $m);// This code is contributed// by anuj_67.?> |
Javascript
<script>// Javascript program to check if // M-th fibonacci divides N-th fibonacci function check(n, m) { // exceptional case for F(2) if (n == 2 || m == 2 || n % m == 0) { document.write("Yes" + "<br>"); } // if none of the above cases, // hence not divisible else { document.write("No" + "<br>"); } } // Driver Code let m = 3, n = 9; check(n, m); // This code is contributed by Mayank Tyagi</script> |
Yes
Time Complexity: O(1).
Auxiliary Space: O(1) as using constant variables
Approach 2: Dynamic Programming:
The Approach first initializes two variables “a” and “b” with values 0 and 1 respectively, and then uses a for loop to calculate the N-th Fibonacci number by adding the previous two numbers in the sequence. It then stores this value in the variable “n_fib”.
Next, the program initializes “a” and “b” again with values 0 and 1 respectively, and uses another for loop to calculate the M-th Fibonacci number in the same way. It stores this value in the variable “m_fib”.
Here is the code:
C++
// C++ program to check if// M-th fibonacci divides N-th fibonacci#include <bits/stdc++.h>using namespace std;void check(int n, int m){ int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } int n_fib = b; a = 0, b = 1; for (int i = 2; i <= m; i++) { c = a + b; a = b; b = c; } int m_fib = b; // exceptional case for F(2) if (n == 2 || m == 2 || n_fib % m_fib == 0) { cout << "Yes" << endl; } // if none of the above cases, // hence not divisible else { cout << "No" << endl; }}// Driver Codeint main(){ int m = 3, n = 6; check(n, m); return 0;} |
Java
import java.util.*;public class Main { public static void main(String[] args) { int m = 3, n = 6; check(n, m); } public static void check(int n, int m) { int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } int n_fib = b; a = 0; b = 1; for (int i = 2; i <= m; i++) { c = a + b; a = b; b = c; } int m_fib = b; // exceptional case for F(2) if (n == 2 || m == 2 || n_fib % m_fib == 0) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
# Python program to check if# M-th fibonacci divides N-th fibonaccidef check(n, m): a, b, c = 0, 1, 0 for i in range(2, n + 1): c = a + b a = b b = c n_fib = b a, b = 0, 1 for i in range(2, m + 1): c = a + b a = b b = c m_fib = b # exceptional case for F(2) if n == 2 or m == 2 or n_fib % m_fib == 0: print("Yes") # if none of the above cases, # hence not divisible else: print("No")# Driver Codem = 3n = 6check(n, m)# This code is contributed by Susobhan Akhuli |
C#
using System;public class GFG { public static void Main(string[] args) { int m = 3, n = 6; Check(n, m); } // check Function dynamic programming approach public static void Check(int n, int m) { int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } int n_fib = b; a = 0; b = 1; for (int i = 2; i <= m; i++) { c = a + b; a = b; b = c; } int m_fib = b; // exceptional case for F(2) if (n == 2 || m == 2 || n_fib % m_fib == 0) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
function check(n, m) { let a = 0, b = 1, c; for (let i = 2; i <= n; i++) { c = a + b; a = b; b = c; } let nFib = b; a = 0; b = 1; for (let i = 2; i <= m; i++) { c = a + b; a = b; b = c; } let mFib = b; // exceptional case for F(2) if (n === 2 || m === 2 || nFib % mFib === 0) { console.log("Yes"); } else { console.log("No"); }}let n = 6, m = 3;check(n, m); |
Yes
Time Complexity: O(n+m), where n and m are the indices of the Fibonacci numbers to be checked.
Auxiliary Space: O(1) as using only constant variables.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
