- Practice
- Mathematics
- Fundamentals
- Is Fibo
- Discussions

# Is Fibo

# Is Fibo

raviatwork + 6 comments Can any one help me to understand test cases 5 to 9. For me all are failing. I tried different values but all passed. Not able to think any conner cases that can fail.

abdullahanam + 1 comment 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.

hakkaboy + 1 comment My submissionis passed for all test cases except TestCase #6 . Seems that the test case is wrong

abhiranjan + 3 comments Nope, it's right. Though it contains some corner case. Check your output for integer which exceeds the range of

*int*.hakkaboy + 3 comments ok I will check , btw I am using BigInteger instead of int

Gnossienne + 1 comment huehuehue unsigned long long int huehuehue

Amateur01 + 1 comment Hey I tried using unsigned long long int..still its failing for TC#6 to TC#9. Could you please help me with this? Thanks

Gnossienne + 0 comments Well unsigned long long int is 64 bits long so thats ~1.84 * 10^19; which is longer than you actually need so... its not an error with length.

vixir + 1 comment Did you solved your problem.I think I have the same problem.

meenu26892 + 1 comment I am also facing the same issue . Anyone solved ?

ahmedysallam + 0 comments Did you solve this problem, Actually facing it too Any Help would be appreciated..

raj_yadav29oct + 1 comment create febbo series first till 50 is enough

then just find input number in series if it is there then print IsFebo else IsNotFebo......find snap code for that

int t =Convert.ToInt32(Console.ReadLine()); // creating Febo series long[] N = new long[100000]; for(long i=0;i<80;i++) { if(i==0) { N[i] = 0; } else if (i == 1) { N[i] = 1; } else { N[i] = N[i - 1] + N[i - 2]; } } while(t>0) { long value = Convert.ToInt64(Console.ReadLine()); if(N.Contains(value)) { Console.WriteLine("IsFibo"); } else Console.WriteLine("IsNotFibo"); t--; }

sumedh0803 + 0 comments how did you figure out that calculating fino series till 50 will be sufficient?

ussmaan_786 + 1 comment In testcase#6 there are 710 inputs but 709 outputs.....kindly check it or correct me if i am wrong

alisa_k + 0 comments [deleted]

ussmaan_786 + 0 comments [deleted]

Vk_BlackCoder + 0 comments use long int N;

dileepreddy + 0 comments you better use long int

philomath213 + 0 comments the problem is the variable type, you should use unsigned long int.

sarathy_v_krish1 + 1 comment 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"; }

rohitkaranaudi + 0 comments Thanks dude.Very Helpful

103_CS3B + 0 comments 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

[deleted] + 3 comments This problem was an eye opener. If you are not connected to your basics about int , long int and how to find a fibnonaci number using "Binet's formula", then you are in trouble in bigger testcases. Also boundry conditions do play an important part. Nice problem!!

TheRyjo + 2 comments 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.

KingLaserFace + 1 comment Yeah memoization is the key.

Once you start caching, speed is never an issue. I just used an array for my look up table and even just doing a linear traversal of it, I was well under the time limit.

arno_lee + 1 comment uh, read about the Binet formula, you can get n-th Fibonacci number in the closed form, no loops needed.

daniel_mclaury + 0 comments The thing about computing using that formula is that you're going to have to do floating-point calculations. This raises a couple of issues:

Can you easily estimate the amount of precision you're going to need to take a small number to a large number and have the rounding error be less than 0.5?

Is it even more efficient to use the closed form? Integer addition and modulo operations are faster than calculating exponentials and logarithms, and the extra storage space is neglible.

RajuDasa + 0 comments Thanks, Your solution helped me. Seems "Binet's formula" has limitation in implementation wise.

kiichi + 0 comments 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.

rocco_Royale123 + 0 comments 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"; }

stempl + 1 comment A number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 â€“ 4) is a perfect square

HaltingProblem + 0 comments Prove it ;)

ftonello + 1 comment Check my implementation for O(1) using C++ meta programming. https://codepair.hackerrank.com/paper/SM4eyT0y?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImZ0b25lbGxvIiwiZW1haWwiOiJldUBmZWxpcGV0b25lbGxvLmNvbSJ9

sachingadagi + 0 comments 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.

kolombaja + 2 comments I had insane reason for failing test cases. Output was saying "terminated due to timeout". That is legit error. But the reason was because i declared some variables with var keyword (C#).

After changing that from "var" to "long" I passed the tests! This has nothing to do with real life since using var keywords does not have performance hits for the code.

dribeas + 0 comments 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`

webkiwi + 0 comments 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.

marmot + 7 comments Solved it by using Binet's formular and fast doubling. This approach is more memory effecient than memorising the entire Fibonacci sequence in your data structure. Speed-wise I am getting an average of 0.14 sec for all test cases in C.

ftonello + 0 comments 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.

brownslink + 0 comments 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.

kishancs46 + 1 comment What do you mean by "fast doubling" can you share links? :-)

marmot + 0 comments Assume the function f(k) calculates the k-th Fibonacci number. If we know f(k) and f(k+1), then we can find:

f(2k) = f(k) * (2*f(k+1) - f(k))

f(2k + 1) = (f(n))^2 + (f(n+1))^2

Reference: https://www.nayuki.io/page/fast-fibonacci-algorithms

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

sidmeister + 0 comments 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.

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

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

arno_lee + 1 comment `func isFib(n: Int) -> Bool { let fiveNSquare: Double = 5*Double(n)*Double(n) return (sqrt(fiveNSquare+4) % 1 == 0) || (sqrt(fiveNSquare-4) % 1 == 0) } for var i = 1; i < textInput.count; i++ { if let n = Int(textInput[i]) { print(isFib(n) ? "IsFibo" : "IsNotFibo") } }`

anshumanc007 + 0 comments why n should be double why not long long int? and then we store n*n in a long double data type variable? why this will not work?

1616410257_cs3e + 1 comment #!/bin/python3 import os import sys # Complete the solve function below. def solve(n): if n in q: return "IsFibo" else: return "IsNotFibo" q=[0] a=0 b=1 for i in range(0,10000): c=a+b a=b b=c q.append(c) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') t = int(input()) for t_itr in range(t): n = int(input()) result = solve(n) fptr.write(result + '\n') fptr.close()

pgmreddy + 0 comments Code looks beautiful.

srinchow + 1 comment failing test case 6 to 9 dont know why any help?

# include

# include

# include

# include

# include

using namespace std;

bool isPerfectSquare(long long x) { long long s = sqrt(x); return (s*s == x); }

bool isFibonacci(long long n) {

`return isPerfectSquare(5LL*n*n + 4) || isPerfectSquare(5LL*n*n - 4);`

}

int main() { long long N; cin >> N;

while (N--) { long long x; cin >> x; if (isFibonacci(x)) cout<<"IsFibo"<

return 0; }

rr47061 + 0 comments use double in place of long long ..

chaubey2ait + 2 comments My test case from 3 to 9 are failing. What is the reason for this?

sourabhmehta2006 + 1 comment 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?

dheeraj + 0 comments please replace this line by

`try { N[j] = Long.parseLong(read.readLine()); } catch (NumberFormatException | IOException e) { // TODO Auto-generated catch block e.printStackTrace(); }`

this line

`N[j] = in.nextLong();`

dheeraj + 0 comments Hi @chaubey2ait,

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

arvindd25 + 1 comment Hello, I am not not sure where is the mistake with my logic. I tried up to some large numbers and they seemed to work correctly. Yes, generating a Fibonacci for every tc was a mistake, but other than that not sure where the mistake was.

First time user asking - apologies for any improprieties.

dheeraj + 0 comments 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.

Sort 307 Discussions, By:

Please Login in order to post a comment