I think the output matched for those testcases could be wrong. I checked against 6. Found one expected output to be wrong. And think it got modified lately.

use long int N;

you better use long int

the problem is the variable type, you should use unsigned long int.

C++ solution :

map<long, long> fibo;
long fibonacci(long n)
{
    if (fibo.find(n)!=fibo.end())    return fibo[n];
    fibo[n]=fibonacci(n-1)+fibonacci(n-2);
    return fibo[n];
}
string solve(long n) {
    fibo[0]=0;
    fibo[1]=1;
    long i=0;
    while(fibonacci(i)<n)
        i++;
    if (fibonacci(i)!=n)    return "IsNotFibo";
    return "IsFibo";
}

if you are doing this with naive method " java.lang.OutOfMemoryError: Java heap space " this will be shown try the custom input 1 123978414 to see this

Fibonacci grows fast enough that all elements from 0 -> 10^10 is only about 50 entries. I just hashed entries from 0 up to the max val asked for and that worked for me.

I checked Binet's formula and it's more elegant;however, since the max 10^10, the number of elements in array is 50, so just straight forward pre-computation should work too.

True.. check this out; string solve(long F) { double root5 = sqrt(5); double phi = (1 + root5) / 2; long nf = (long)(log(F*root5) / log(phi) + 0.5 ); long Fn = (long)( pow(phi, nf)/root5 + 0.5);
if (Fn==F) return "IsFibo"; else return "IsNotFibo"; }

Prove it ;)

Hi,I am not able to see your implementation,the page shows error-with code 4001. Will you please paste it somewhere else, like pastebin? . Thanks & Regards.

What is the type that will be deduced if you use var? Is your algorithm terminating when the intermediate value exceeds the range of the variable you have? There is no difference between using var vs. a real type, but there are differences between using int and long

I believe that you can use var, however, when you set the initial values, you have to let the compiler know that it is a long rather than an int.

For example:

var foo = 0; // foo is an int

var foo = 0L; // foo is a long

Once it has been implicitly typed, it remains that way.

How is that more efficient? The entire fibonacci sequence for this problem are 50 entries only. Check my implementation for compiler generated fibonacci sequence, so O(1) at all times.

I got an average of 0.02 s using Python. The key is evaluating whether or no 5*x*x+4 or 5*x*x-4 is a perfect square.

What do you mean by "fast doubling" can you share links? :-)

Err, my worst case was 0.02s, using PHP. 0.14s for C is not good at all. =/

No way. Computing golden ratio will take valuable cycles. All those irrational numbers will make it a mess, since floating point calculations take much heavier toll and are more susceptible to errors. And, in the given range, there are only 50 fibonaccis to compute max. Even then, you can opt for a compute and extend the dictionary as you go method.

just used double numbers and coded the 5x^2 +/- 4 formulas outright, works very good

how did you check the floating point precision for irrational no. like root(5).?

Code looks beautiful.

use double in place of long long ..

same issue. i downloaded Test case 3 its perfectly fine in my system . but here it is saying wrong answer. did you find reason for it?

Hi @chaubey2ait,

you can download the testcases and debug your code. You can watch the video here about it here

Check for this input

2
8
3

both are fibonacci numbers. But your code is printing that 3 is non-fibo. Also, you are assuming that the input given is always in increasing order of fibonacci series but it is not the case. Please fix your code.