(Algorithm) How many Fibonacci numbers exist less than a given number?

Question: How many Fibonacci numbers exist less than a given number 'n'?

Ex. n = 4

{0, 1, 1, 2, 3}

5 numbers

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: Rahul Sharma

ANSWER

First of all, we should understand how Fibonacci numbers occur. (In modern usage) they start with 0 and 1. After this two numbers, they continue as sum of previous numbers. Let's see:

0, 1,...

0 + 1 = 1

0, 1, 1,...

1 + 1 = 2

0, 1, 1, 2,...

2 + 1 = 3

0, 1, 1, 2, 3,...

3 + 2 = 5

0, 1, 1, 2, 3, 5,...

I think you can continue easily from this point. From this series, we understand that we should start with two variable; (ex. x and y) and we should have counter to count, and n to number will be checked.

x = 0, y = 1, n = input, counter = 0

They are our first entries. And they build our previous numbers by using each other!

If (n > 0), we print x and increase counter by 1. If (n>1) we print y and increase counter by 1. For following numbers we can use for loop, because we have only condition to check and regularity. First we swap x and y. Because our y will be our x for next step. Then we assign (x + y) to y, then check if y is less than n. According to this, we increase counter and print y or break the loop.