# Is Fibo Solution

Problem
You are given an integer, N. Write a program to determine if N is an element of the Fibonacci sequence.
The first few elements of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13….

###### Input

The first line of input contains a single integer T, number of test cases. T lines follow.
Each line contains an integer n.

###### Output

Output IsFibo – if n is a Fibonacci number,
Output IsNotFibo – if n is not a Fibonacci number,

###### Constraints
• 1 ≤ T ≤ 100000
• 1 ≤ n ≤ 1010
###### Sample Input
3
5
7
8
###### Sample Output
IsFibo
IsNotFibo
IsFibo
###### Solution

The idea is to store all fibonacci numbers upto 50th fibonacci number in a map. The catch is that 50th fibonacci number is greater than 1010, which is 12,586,269,025

Code Implementation

//
//  main.cpp
//  IsFibo
//
//  Created by Himanshu on 16/02/22.
//

#include<iostream>
#include<map>
using namespace std;

int main()
{
int T;
long long tmp1, tmp2, n;
map<long long, bool> fiboMap;
map<long long, bool>::iterator it;

tmp1 = 0;
tmp2 = 1;
fiboMap[tmp1] = 1;
fiboMap[tmp2] = 1;

for (int i=0; i<=50; i++) {
long long tmp3 = tmp1 + tmp2;
fiboMap[tmp3] = 1;
tmp1 = tmp2;
tmp2 = tmp3;
}

cin>>T;

while (T--) {
cin>>n;

it = fiboMap.find(n);

if (it != fiboMap.end()) {
cout<<"IsFibo"<<endl;
} else {
cout<<"IsNotFibo"<<endl;
}

}

return 0;
}