Check if a number is fibonacci number or not
The Fibonacci sequence is a series of numbers in which each number (after the first two) is the sum of the two preceding ones. In this article, we will discuss how to check if a given number is a Fibonacci number or not. We will provide an explanation of the problem statement, suitable examples, an algorithm with pseudocode, and an explanation of the resultant output with the time complexity of the code.
Problem Statement
We are given a number, and we need to determine whether it is a Fibonacci number or not. A Fibonacci number is any number that is present in the Fibonacci sequence.
The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the previous two numbers. The sequence begins as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
If a number exists in this sequence, it is considered a Fibonacci number.
Example
Let's consider a few examples to understand the problem:
- Input: 51
- Input: 144
- Input: 987
- Input: 14
Output: 51 is not a Fibonacci number
Explanation: The Fibonacci sequence does not include 51.
Output: 144 is a Fibonacci number
Explanation: 144 is present in the Fibonacci sequence.
Output: 987 is a Fibonacci number
Explanation: 987 is present in the Fibonacci sequence.
Output: 14 is not a Fibonacci number
Explanation: The Fibonacci sequence does not include 14.
Algorithm
To check if a number is a Fibonacci number or not, we can follow the below algorithm:
- Initialize the variables "first" and "second" with the values 0 and 1 respectively.
- Initialize the variable "status" to 0.
- While the value of "first" is less than or equal to the given number:
- If the value of "first" is equal to the given number, set "status" to 1 and break the loop.
- Calculate the next Fibonacci number by adding "first" and "second".
- Update the value of "first" as the difference between "second" and "first".
- Return the value of "status".
Pseudocode
function isFibonacci(number):
first = 0
second = 1
status = 0
while first <= number:
if first == number:
status = 1
break
next_fibonacci = first + second
first = second - first
return status
function checkFibonacci(number):
if isFibonacci(number) == 0:
print number, "is not a Fibonacci number"
else:
print number, "is a Fibonacci number"
checkFibonacci(51)
checkFibonacci(144)
checkFibonacci(987)
checkFibonacci(14)
Code Solution
Here given code implementation process.
//C Program
//Check if a number is fibonacci number or not
#include <stdio.h>
//check whether number is a Fibonacci number
int fibonacci(int n)
{
//Set the initial value of variable
//This is two initial value
int first = 0;
int second = 1;
int status = 0;
while(first<=n)
{
if(first==n)
{
status=1;
break;
}
//This is next result
second += first;
first = second - first;
}
return status;
}
//Controlling the request of fibonacci number
void is_fibonacci(int number)
{
if(fibonacci(number)==0)
{
printf("%d Is not a fibonacci number\n",number);
}
else
{
printf("%d Is a fibonacci number\n",number);
}
}
int main()
{
is_fibonacci(51);
is_fibonacci(144);
is_fibonacci(987);
is_fibonacci(14);
return 0;
}
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
/*
C++ Program
Check if a number is fibonacci number or not
*/
#include<iostream>
using namespace std;
class MyNumber {
public:
//check whether number is a Fibonacci number
bool fibonacci(int n) {
//Set the initial value of variable
//This is two initial value
int first = 0;
int second = 1;
bool status = false;
while (first <= n) {
if (first == n) {
status = true;
break;
}
//This is next result
second += first;
first = second - first;
}
return status;
}
//Controlling the request of fibonacci number
void is_fibonacci(int number) {
if (this->fibonacci(number) == false) {
cout << number << " Is not a fibonacci number\n";
} else {
cout << number << " Is a fibonacci number\n";
}
}
};
int main() {
MyNumber obj ;
//Test case
obj.is_fibonacci(51);
obj.is_fibonacci(144);
obj.is_fibonacci(987);
obj.is_fibonacci(14);
return 0;
}
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
/*
Java Program
Check if a number is fibonacci number or not
*/
public class MyNumber {
//check whether number is a Fibonacci number
public boolean fibonacci(int n) {
//Set the initial value of variable
//This is two initial value
int first = 0;
int second = 1;
boolean status = false;
while (first <= n) {
if (first == n) {
status = true;
break;
}
//This is next result
second += first;
first = second - first;
}
return status;
}
//Controlling the request of fibonacci number
public void is_fibonacci(int number) {
if (fibonacci(number) == false) {
System.out.print(number + " Is not a fibonacci number\n");
} else {
System.out.print(number + " Is a fibonacci number\n");
}
}
public static void main(String[] args) {
MyNumber obj = new MyNumber();
//Test case
obj.is_fibonacci(51);
obj.is_fibonacci(144);
obj.is_fibonacci(987);
obj.is_fibonacci(14);
}
}
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
/*
C# Program
Check if a number is fibonacci number or not
*/
using System;
public class MyNumber {
//check whether number is a Fibonacci number
public Boolean fibonacci(int n) {
//Set the initial value of variable
//This is two initial value
int first = 0;
int second = 1;
Boolean status = false;
while (first <= n) {
if (first == n) {
status = true;
break;
}
//This is next result
second += first;
first = second - first;
}
return status;
}
//Controlling the request of fibonacci number
public void is_fibonacci(int number) {
if (fibonacci(number) == false) {
Console.Write(number + " Is not a fibonacci number\n");
} else {
Console.Write(number + " Is a fibonacci number\n");
}
}
public static void Main(String[] args) {
MyNumber obj = new MyNumber();
//Test case
obj.is_fibonacci(51);
obj.is_fibonacci(144);
obj.is_fibonacci(987);
obj.is_fibonacci(14);
}
}
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
# Python 3 Program
# Check if a number is fibonacci number or not
class MyNumber :
#check whether number is a Fibonacci number
def fibonacci(self, n) :
#This is two initial value
#Set the initial value of variable
first = 0
second = 1
status = False
while (first <= n) :
if (first == n) :
status = True
break
#This is next result
second += first
first = second - first
return status
#Controlling the request of fibonacci number
def is_fibonacci(self, number) :
if (self.fibonacci(number) == False) :
print(number ," Is not a fibonacci number\n")
else :
print(number ," Is a fibonacci number\n")
def main() :
obj = MyNumber()
#Test case
obj.is_fibonacci(51)
obj.is_fibonacci(144)
obj.is_fibonacci(987)
obj.is_fibonacci(14)
if __name__ == "__main__":
main()
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
# Ruby Program
# Check if a number is fibonacci number or not
class MyNumber
#check whether number is a Fibonacci number
def fibonacci(n)
#This is two initial value
#Set the initial value of variable
first = 0
second = 1
status = false
while (first <= n)
if (first == n)
status = true
break
end
#This is next result
second += first
first = second - first
end
return status
end
#Controlling the request of fibonacci number
def is_fibonacci(number)
if (self.fibonacci(number) == false)
print(number ," Is not a fibonacci number\n")
else
print(number ," Is a fibonacci number\n")
end
end
end
def main()
obj = MyNumber.new()
#Test case
obj.is_fibonacci(51)
obj.is_fibonacci(144)
obj.is_fibonacci(987)
obj.is_fibonacci(14)
end
main()
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
/*
Scala Program
Check if a number is fibonacci number or not
*/
import scala.util.control.Breaks._
class MyNumber {
//check whether number is a Fibonacci number
def fibonacci(n: Int): Boolean = {
//Set the initial value of variable
//This is two initial value
var first: Int = 0;
var second: Int = 1;
var status: Boolean = false;
breakable {
while (first <= n) {
if (first == n) {
status = true;
break;
}
//This is next result
second += first;
first = second - first;
}
}
return status;
}
//Controlling the request of fibonacci number
def is_fibonacci(number: Int): Unit = {
if (this.fibonacci(number) == false) {
print(s"$number Is not a fibonacci number\n");
} else {
print(s"$number Is a fibonacci number\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyNumber = new MyNumber();
//Test case
obj.is_fibonacci(51);
obj.is_fibonacci(144);
obj.is_fibonacci(987);
obj.is_fibonacci(14);
}
}
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
/*
Swift 4 Program
Check if a number is fibonacci number or not
*/
class MyNumber {
//check whether number is a Fibonacci number
func fibonacci(_ n: Int) -> Bool {
//Set the initial value of variable
//This is two initial value
var first: Int = 0;
var second: Int = 1;
var status: Bool = false;
while (first <= n) {
if (first == n) {
status = true;
break;
}
//This is next result
second += first;
first = second - first;
}
return status;
}
//Controlling the request of fibonacci number
func is_fibonacci(_ number: Int) {
if (self.fibonacci(number) == false) {
print(number ," Is not a fibonacci number");
} else {
print(number ," Is a fibonacci number");
}
}
}
func main() {
let obj: MyNumber = MyNumber();
//Test case
obj.is_fibonacci(51);
obj.is_fibonacci(144);
obj.is_fibonacci(987);
obj.is_fibonacci(14);
}
main();
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
<?php
/*
Php Program
Check if a number is fibonacci number or not
*/
class MyNumber {
//check whether number is a Fibonacci number
public function fibonacci($n) {
//Set the initial value of variable
//This is two initial value
$first = 0;
$second = 1;
$status = false;
while ($first <= $n) {
if ($first == $n) {
$status = true;
break;
}
//This is next result
$second += $first;
$first = $second - $first;
}
return $status;
}
//Controlling the request of fibonacci number
public function is_fibonacci($number) {
if ($this->fibonacci($number) == false) {
echo($number ." Is not a fibonacci number\n");
} else {
echo($number ." Is a fibonacci number\n");
}
}
};
function main() {
$obj = new MyNumber();
//Test case
$obj->is_fibonacci(51);
$obj->is_fibonacci(144);
$obj->is_fibonacci(987);
$obj->is_fibonacci(14);
}
main();
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
/*
Node Js Program
Check if a number is fibonacci number or not
*/
class MyNumber {
//check whether number is a Fibonacci number
fibonacci(n) {
//Set the initial value of variable
//This is two initial value
var first = 0;
var second = 1;
var status = false;
while (first <= n) {
if (first == n) {
status = true;
break;
}
//This is next result
second += first;
first = second - first;
}
return status;
}
//Controlling the request of fibonacci number
is_fibonacci(number) {
if (this.fibonacci(number) == false) {
process.stdout.write(number + " Is not a fibonacci number\n");
} else {
process.stdout.write(number + " Is a fibonacci number\n");
}
}
}
function main(args) {
var obj = new MyNumber();
//Test case
obj.is_fibonacci(51);
obj.is_fibonacci(144);
obj.is_fibonacci(987);
obj.is_fibonacci(14)
}
main();
Output
51 Is not a fibonacci number
144 Is a fibonacci number
987 Is a fibonacci number
14 Is not a fibonacci number
Resultant Output
The output of the given code will be as follows:
51 is not a Fibonacci number 144 is a Fibonacci number 987 is a Fibonacci number 14 is not a Fibonacci number
The code checks each number by iteratively calculating Fibonacci numbers until the calculated number is greater than the given input. If the calculated number is equal to the input, it is considered a Fibonacci number. The time complexity of this code is O(n), where n is the given number. The code iterates through the Fibonacci sequence until it reaches or surpasses the given number. Therefore, the time complexity is linear with respect to the input.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment