We are given a variable n, we need to find whether Fibonacci number will be a multiple of 10 or not.
Examples:
Input : 15
Output : Yes
Input : 17
Output : No
A Simple Method is to find the nth Fibonacci number and check if it is divisible by 10 or not.
C++
#include<bits/stdc++.h>
int fibonacci(int n)
{
int a = 0, b = 1, c;
if (n <= 1)
return n;
for (int i = 2; i<= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
bool isMultipleOf10(int n)
{
int f = fibonacci(30);
return (f % 10 == 0);
}
int main()
{
int n = 30;
if (isMultipleOf10(n))
printf("Yes\n");
else
printf("No\n");
}
|
Java
class Fibonacci
{
static int fibonacci(int n)
{
int a = 0;
int b=1;
int c=0;
if (n <= 1)
return n;
for (int i = 2; i<= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
static boolean isMultipleOf10(int n)
{
int f = fibonacci(30);
return (f % 10 == 0);
}
public static void main (String[] args)
{
int n = 30;
if (isMultipleOf10(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
|
Python 3
def fibonacci(n):
a = 0
b = 1
if (n <= 1):
return n
for i in range(2, n + 1):
c = a + b
a = b
b = c
return c
def isMultipleOf10(n):
f = fibonacci(30)
return (f % 10 == 0)
if __name__ =="__main__":
n = 30
if (isMultipleOf10(n)):
print("Yes")
else:
print("No")
|
C#
using System;
class GFG {
static int fibonacci(int n)
{
int a = 0;
int b = 1;
int c = 0;
if (n <= 1)
return n;
for (int i = 2; i<= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
static bool isMultipleOf10(int n)
{
int f = fibonacci(30);
return (f % 10 == 0);
}
public static void Main ()
{
int n = 30;
if (isMultipleOf10(n))
Console.Write("Yes");
else
Console.Write("No");
}
}
|
PHP
<?php
function fibonacci($n)
{
$a = 0; $b = 1; $c;
if ($n <= 1)
return $n;
for ($i = 2; $i<= $n; $i++)
{
$c = $a + $b;
$a = $b;
$b = $c;
}
return $c;
}
function isMultipleOf10($n)
{
$f = fibonacci(30);
return ($f % 10 == 0);
}
$n = 30;
if (isMultipleOf10($n))
echo "Yes\n";
else
echo "No\n";
?>
|
Javascript
<script>
function fibonacci(n)
{
let a = 0;
let b = 1;
let c;
if (n <= 1)
return n;
for (let i = 2; i<= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
function isMultipleOf10(n)
{
let f = fibonacci(30);
return (f % 10 == 0);
}
let n = 30;
if (isMultipleOf10(n))
document.write("Yes<br>");
else
document.write("No\n");
</script>
|
Time complexity: O(n)
Auxiliary space: O(1)
Efficient Method :
The above solution may not work if n is very large, then it is not possible to find fibonacci number. Moreover, we can check without finding fibonacci number by looking on the pattern. Let’s see how !
If number is divisible by 10, then it must have to be divisible by 5 and 2 both.
Multiples of 2 in Fibonacci Series :
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 ….
The number shown in bold are divisible by 2. On careful observation, we finds that every 3rd number is divisible by 2.
Multiples of 5 in Fibonacci Series :
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 ……
The number shown in bold are divisible by 5. On careful observation, we find that every 5-th number is divisible by 5.
Now LCM of 3 and 5 is 15. So, every 15-th Fibonacci number will be divisible by 10. So, we don’t need to find Fibonacci number, just we have to check if n is divisible by 15 or not.
Below is the implementation.
C++
#include<bits/stdc++.h>
bool isMultipleOf10(int n)
{
return (n % 15 == 0);
}
int main()
{
int n = 30;
if (isMultipleOf10(n))
printf("Yes\n");
else
printf("No\n");
return 0;
}
|
Java
class Fibonacci
{
static boolean isMultipleOf10(int n)
{
if(n%15 == 0)
return true;
return false;
}
public static void main (String[] args)
{
int n = 30;
if (isMultipleOf10(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
|
Python3
def isMultipleOf10(n):
return (n % 15 == 0)
n = 30
if (isMultipleOf10(n)):
print("Yes");
else:
print("No");
|
C#
using System;
class GFG {
static bool isMultipleOf10(int n)
{
if(n % 15 == 0)
return true;
return false;
}
public static void Main ()
{
int n = 30;
if (isMultipleOf10(n))
Console.Write("Yes");
else
Console.Write("No");
}
}
|
PHP
<?php
function isMultipleOf10($n)
{
return ($n % 15 == 0);
}
$n = 30;
if (isMultipleOf10($n))
echo "Yes\n";
else
echo "No\n";
?>
|
Javascript
function isMultipleOf10(n)
{
return (n % 15 == 0);
}
let n = 30;
if (isMultipleOf10(n))
document.write("Yes<br>");
else
document.write("No<br>");
|
Time Complexity: O(1) time.
Auxiliary space: O(1)
This article is contributed by Aditya Kumar. 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!
