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++
#include <bits/stdc++.h>
using namespace std;
void check( int n, int m)
{
if (n == 2 || m == 2 || n % m == 0) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
int main()
{
int m = 3, n = 9;
check(n, m);
return 0;
}
|
Java
import java.io.*;
class GFG
{
static void check( int n, int m)
{
if (n == 2 || m == 2 ||
n % m == 0 )
{
System.out.println( "Yes" );
}
else
{
System.out.println( "No" );
}
}
public static void main (String[] args)
{
int m = 3 , n = 9 ;
check(n, m);
}
}
|
Python 3
def check(n, m):
if (n = = 2 or m = = 2 or
n % m = = 0 ) :
print ( "Yes" )
else :
print ( "No" )
m = 3
n = 9
check(n, m)
|
C#
using System;
class GFG
{
static void check( int n, int m)
{
if (n == 2 || m == 2 ||
n % m == 0)
{
Console.WriteLine( "Yes" );
}
else
{
Console.WriteLine( "No" );
}
}
public static void Main ()
{
int m = 3, n = 9;
check(n, m);
}
}
|
PHP
<?php
function check( $n , $m )
{
if ( $n == 2 || $m == 2 ||
$n % $m == 0)
{
echo "Yes" , "\n" ;
}
else
{
echo "No" , " \n" ;
}
}
$m = 3; $n = 9;
check( $n , $m );
?>
|
Javascript
<script>
function check(n, m)
{
if (n == 2 || m == 2 || n % m == 0) {
document.write( "Yes" + "<br>" );
}
else {
document.write( "No" + "<br>" );
}
}
let m = 3, n = 9;
check(n, m);
</script>
|
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”.
C++
#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;
if (n == 2 || m == 2 || n_fib % m_fib == 0) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
int 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;
if (n == 2 || m == 2 || n_fib % m_fib == 0 ) {
System.out.println( "Yes" );
} else {
System.out.println( "No" );
}
}
}
|
Python3
def 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
if n = = 2 or m = = 2 or n_fib % m_fib = = 0 :
print ( "Yes" )
else :
print ( "No" )
m = 3
n = 6
check(n, m)
|
C#
using System;
public class GFG {
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;
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;
if (n === 2 || m === 2 || nFib % mFib === 0) {
console.log( "Yes" );
} else {
console.log( "No" );
}
}
let n = 6, m = 3;
check(n, m);
|
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.
Contact Us