Non Fibonacci Numbers in Java

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)

First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141,....

Examples:

Input : n = 2
Output : 6

Input : n = 5
Output : 10

There are basically two solutions for it,

Naive Approach: First Approach is to find find Fibonacci numbers and then print first n numbers not present in the found Fibonacci numbers.

Better Solution: A 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.

Solution:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class FibonaciNumber
{
public static int nonFibonaciNumber(int n)
{
int prevprev=1,prev=2,current=3;

while(n>0)
{
prevprev=prev;
prev=current;
current=prevprev + prev;
n=n-(current-prev-1); //it can be negative
}
n=n+(current-prev-1); //make it positive

return prev+n;
}

public static void main(String[] args)
{
int count=nonFibonaciNumber(5);
System.out.println(count);
}

}

Output: 10