Am I a Fibonacci Number
All submissions for this problem are available.
Read problems statements in Russian here
The Head Chef has been playing with Fibonacci numbers for long . He has learnt several tricks related to Fibonacci numbers . Now he wants to test his chefs in the skills .
A fibonacci number is defined by the recurrence :
f(n) = f(n-1) + f(n-2) for n > 2
and f(1) = 0
and f(2) = 1 .
Given a number A , determine if it is a fibonacci number.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The only line of each test case contains a single integer A denoting the number to be checked .
- For each test case, output a single line containing "YES" if the given number is a fibonacci number , otherwise output a single line containing "NO" .
- 1 ≤ T ≤ 1000
- 1 ≤ number of digits in A ≤ 1000
- The sum of number of digits in A in all test cases <= 10000.
Input: 3 3 4 5 Output: YES NO YES
Example case 1. The first few fibonacci numbers are 0 , 1 , 1 , 2 , 3 ,5 , 8 , 13 and so on and the series is increasing . Only 3 and 5 appear in this series while 4 does not appear in the series .
|Tags||binary-search, cook40, easy, fibonacci, hashing, offline, vineetpaliwal|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.