Given a positive integer N, your 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)
Example 1:
Input: N = 5
Output: 10
Explaination: The first 5 non-fibonacci 
numbers are 4, 6, 7, 9, 10.
Example 2:
Input: N = 15
Output: 22
Explaination: The fibonacci numbers 
are 1, 2, 3, 5, 8, 13, 21, 34. Here 
22 becomes the 15th non-fibonacci 
number.
Your Task:
You do not need to read input or print anything. Your task is to complete the function nonFibonacci() which takes the value N and returns the Nth non-fibonacci number.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def nonFibonacci(self, N):

        # code here

Solutions:
class Solution:

	def nonFibonacci(self, N):
		(a, b) = (3, 5)
		while N - b + a + 1 > 0:
			N -= b - a - 1
			(a, b) = (b, a + b)
		return a + N


class Solution:

	def nonFibonacci(self, n):
		(a, b) = (0, 1)
		l = [0, 1]
		l2 = []
		while n > b - 1:
			c = a + b
			n -= b - 1
			a = b
			b = c
		c = a + b
		return c + n


class Solution:

	def nonFibonacci(self, N):
		(a, b) = (1, 1)
		while N > b - 1:
			c = a + b
			N = N - (b - 1)
			a = b
			b = c
		c = a + b
		return c + N


class Solution:

	def nonFibonacci(self, N):
		f = [1, 2]
		c = 0
		for i in range(2, N + 5):
			f.append(f[i - 1] + f[i - 2])
			c = c + (f[i - 1] - f[i - 2] - 1)
			if c >= N:
				return f[i - 2] + (N - (c - (f[i - 1] - f[i - 2] - 1)))


class Solution:

	def nonFibonacci(self, N):
		prevPrev = 1
		prev = 2
		curr = 3
		l = []
		while N > 0:
			prevPrev = prev
			prev = curr
			curr = prevPrev + prev
			N = N - (curr - prev - 1)
		N = N + (curr - prev - 1)
		return prev + N


class Solution:

	def nonFibonacci(self, N):
		a = 1
		b = 2
		c = 3
		n = N
		while n > 0:
			a = b
			b = c
			c = a + b
			n -= c - b - 1
		n += c - b - 1
		return b + n