## Friday, September 16, 2016

### Non Fibonacci Numbers - GeeksforGeeks

Non Fibonacci Numbers - GeeksforGeeks
Given a positive integer n, the task is to print the n'th non Fibonacci number. The Fibonacci numbers are defined as:
`Fib(0) = 0  Fib(1) = 1  for n >1, Fib(n) = Fib(n-1) + Fib(n-2) `

A naive solution is to find find Fibonacci numbers and then print first n numbers not present in the found Fibonacci numbers.
better solution is to use the formula of Fibonacci numbers and keep adding of gap between two consecutive Fibonacci numbers. Value of sum of gap is count of non-fibonacci numbers seen so far.
`int` `nonFibonacci(``int` `n)`
`{`
`    ``// curr is to keep track of current fibonacci`
`    ``// number, prev is previous, prevPrev is`
`    ``// previous of previous.`
`    ``int` `prevPrev=1, prev=2, curr=3;`

`    ``// While count of non-fibonacci numbers`
`    ``// doesn't become negative or zero`
`    ``while` `(n > 0)`
`    ``{`
`        ``// Simple Fibonacci number logic`
`        ``prevPrev = prev;`
`        ``prev = curr;`
`        ``curr = prevPrev + prev;`

`        ``// (curr - prev - 1) is count of`
`        ``// non-Fibonacci numbers between curr`
`        ``// and prev.`
`        ``n = n - (curr - prev - 1);`
`    ``}`

`    ``// n might be negative now. Make sure it`
`    ``// becomes positive by removing last added`
`    ``// gap.`
`    ``n = n + (curr - prev - 1);`

`    ``// n must be now positive and less than or equal`
`    ``// to gap between current and previous, i.e., `
`    ``// (curr - prev - 1);`

`    ``// Now add the positive n to previous Fibonacci`
`    ``// number to find the n'th non-fibonacci.`
`    ``return` `prev + n;`
`}`