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