Non Fibonacci Numbers in Java

Given a positive integer n, the task is to print the nth 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

#Java #NonFibonaccinumber