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….

Hackerrank Problem Link

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 ≤ 10^10

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 10^10, which is 12,586,269,025

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

Leave a Reply

Your email address will not be published.