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.

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.

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;

}

Read full article from Non Fibonacci Numbers - GeeksforGeeks