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

Output: 51 is not a Fibonacci number

Explanation: The Fibonacci sequence does not include 51.

• Input: 144

Output: 144 is a Fibonacci number

Explanation: 144 is present in the Fibonacci sequence.

• Input: 987

Output: 987 is a Fibonacci number

Explanation: 987 is present in the Fibonacci sequence.

• Input: 14

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:

1. Initialize the variables "first" and "second" with the values 0 and 1 respectively.
2. Initialize the variable "status" to 0.
3. 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".
4. 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
• C++
• Java
• C#
• Python
• Ruby
• Scala
• Swift 4
• Php
• Node Js

//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;
}

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;
}

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);
	}
}

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);
	}
}

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()

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()

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);
	}
}

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();

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();

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();

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.