1

doing some practice technical tests for interviews but I have been asked to find if a number is in the Fibonacci sequence without using a loop or square root. I have done an implementation with loops but does not count. so how am I supposed to go about it unless I have infinite if statements?

mdimran
  • 23
  • 2
  • Recursion isn’t usually considered a loop. – Victor Wilson Oct 21 '21 at 20:48
  • 1
    @VictorWilson: Of course it's a loop. How could it be otherwise? That's how functional programming languages like lisp are able to loop without using an explicit loop construct like `for` or `while`. – Robert Harvey Oct 21 '21 at 20:50
  • 2
    @RobertHarvey It is a loop but as thye said, it is often not considered a loop. For example in homework questions that say _"dont use loops"._ – Zabuzard Oct 21 '21 at 20:51
  • 1
    Create a list, or download one, of fibanacci numbers up to Integer.MAX_VALUE and save it in a text file. Then have your program check if your element is in the list. I'm sure there is a loop in there though. – matt Oct 21 '21 at 20:53
  • @RobertHarvey I submit a language like Lisp cannot iterate through lists of items; it can only recurse through them. Maybe it’s a semantic difference - while the end result is the same, they occupy different sectors of my brain. – Victor Wilson Oct 23 '21 at 17:57

1 Answers1

2

This may seem like cheating, but if it isn't 1 then check whether Math.round(x * 2.23606797749979)) when squared gives you 5*x*x+4 or 5*x*x-4.

The reason why is that 5 times a Fibonacci number +- 4 has to be a perfect square. And if x is at all large, the only number which, when squared, could possibly do it is the closest integer to x*sqrt(5). And "at all large" works out to be larger than 1.

btilly
  • 43,296
  • 3
  • 59
  • 88
  • I do wonder how knowing this makes one a better candidate in a technical interview, unless the position requires an extensive math background. – Robert Harvey Oct 23 '21 at 18:04
  • @RobertHarvey It is a terrible interview question. If I was asked it, that would be a strike against my interviewer. – btilly Oct 23 '21 at 21:54