Non Fibonacci Numbers
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
Below is the implementation of the above idea.
C++
// C++ program to find n'th Fibonacci number #include <bits/stdc++.h> using namespace std; // Returns n'th Non-Fibonacci number 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; } // Driver code int main() { cout << nonFibonacci(5); return 0; } |
C
// C program to find n'th Fibonacci number #include<stdio.h> // Returns n'th Non-Fibonacci number 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; } // Driver code int main() { printf ( "%d" ,nonFibonacci(5)); return 0; } // This code is contributed by allwink45. |
Java
// Java program to find // n'th Fibonacci number import java.io.*; class GFG { // Returns n'th Non- // Fibonacci number static 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; } // Driver Code public static void main(String args[]) { System.out.println(nonFibonacci( 5 )); } } // This code is contributed by aj_36 |
Python
# Python program to find n'th # Fibonacci number # Returns n'th Non-Fibonacci # number def nonFibonacci(n): # curr is to keep track of # current fibonacci number, # prev is previous, prevPrev # is previous of previous. prevPrev = 1 prev = 2 curr = 3 # While count of non-fibonacci # numbers doesn't become # negative or zero while n > 0 : 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 # Driver code print (nonFibonacci( 5 )) # This code is contributed by anuj_67. |
C#
// C# program to find // n'th Fibonacci number using System; class GFG { // Returns n'th Non- // Fibonacci number static 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; } // Driver Code public static void Main () { Console.WriteLine (nonFibonacci(5)); } } //This code is contributed by aj_36 |
Javascript
<script> // Javascript program to find n'th Fibonacci number // Returns n'th Non-Fibonacci number function nonFibonacci(n) { // curr is to keep track of current fibonacci // number, prev is previous, prevPrev is // previous of previous. let 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; } // Driver code document.write(nonFibonacci(5)); // This code is contributed by Mayank Tyagi </script> |
PHP
<?php // PHP program to find // n'th Fibonacci number // Returns n'th Non- // Fibonacci number function nonFibonacci( $n ) { // curr is to keep track of // current fibonacci number, // prev is previous, prevPrev // is previous of previous. $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 ; } // Driver code echo nonFibonacci(5); // This code is contributed by m_kit ?> |
Output :
10
Time Complexity : O(n) , Auxiliary Space : O(1)
Now Beginner you must be wondering what if we were supposed to print Non-Fibonacci Series in a range, then the code is as follows:
C++
#include <iostream> using namespace std; int main() { int i = 0, j = 1, k, m, no, b[10]; // Range is 10 no = 10; b[1] = 0; b[2] = 1; // Check if range is less equals to 1 if (no <= 1) { cout << "You have enter a wrong range" ; } // check if range is greater than 1 // and less equals to 5 else if (no <= 5 && no > 1) { cout << "\nThere is not any Non-Fibonacci series " "that lies between 1 to " << no << " term of Fibonacci Series." ; } // If range is greater than 5 else { // Loop to calculate fibonacci series till // range for (m = 2; m < no; m++) { k = i + j; i = j; j = k; // Store fibonacci series into b[] // array b[m] = k; } i = 5; cout << "\nThe Non-Fibonacci series that lies " "between 1 to " << no << " term of Fibonacci Series is: \n" ; // Loop to calculate Non-Fibonacci // series for ( int ans = 4; ans < b[no - 1]; ans++) { if (ans != b[i]) // Print Non-Fibonacci Series cout << ans << " " ; else i++; } } return 0; } |
C
#include <stdio.h> #include <stdlib.h> int main() { int i = 0, j = 1, k, m, no, b[10]; // Range is 10 no = 10; b[1] = 0; b[2] = 1; // Check if range is less equals to 1 if (no <= 1) { printf ( "You have enter a wrong range" ); } // check if range is greater than 1 and less equals to 5 else if (no <= 5 && no > 1) { printf ( "\nThere is not any Non-Fibonacci series " "that lies between 1 to %d term of " "Fibonacci Series." , no); } // If range is greater than 5 else { // Loop to calculate fibonacci series till range for (m = 2; m < no; m++) { k = i + j; i = j; j = k; // Store fibonacci series into b[] array b[m] = k; } i = 5; printf ( "\nThe Non-Fibonacci series that lies between " "1 to %d term of Fibonacci Series is: \n" , no); // Loop to calculate Non-Fibonacci series for ( int ans = 4; ans < b[no - 1]; ans++) { if (ans != b[i]) // Print Non-Fibonacci Series printf ( "%d " , ans); else i++; } } return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { int [] holes = { 21 , 3 , 6 }; int i = 0 , j = 1 , k, m, no; int [] b = new int [ 10 ]; // Range is 10 no = 10 ; b[ 1 ] = 0 ; b[ 2 ] = 1 ; // Check if range is less equals to 1 if (no <= 1 ) { System.out.print( "You have enter a wrong range" ); } // check if range is greater than 1 // and less equals to 5 else if (no <= 5 && no > 1 ) { System.out.print( "\n" + "There is not any Non-Fibonacci series that lies between 1 to" + no + " term of Fibonacci Series." ); } // If range is greater than 5 else { // Loop to calculate fibonacci series till // range for (m = 2 ; m < no; m++) { k = i + j; i = j; j = k; // Store fibonacci series into b[] // array b[m] = k; } i = 5 ; System.out.println( "\n" + "The Non-Fibonacci series that lies between 1 to " + no + " term of Fibonacci Series is: " + "\n" ); // Loop to calculate Non-Fibonacci // series for ( int ans = 4 ; ans < b[no - 1 ]; ans++) { if (ans != b[i]) // Print Non-Fibonacci Series System.out.print(ans + " " ); else i++; } } } // This Solution is contributed by shinjanpatra. |
Python3
i = 0 j = 1 b = [] no = 10 # Range is 10 b.append( 0 ) b.append( 1 ) if (no < = 1 ): # Check if range is less equals to 1 print ( "You have enter a wrong range..." ) elif (no < = 5 and no > 1 ): # check if range is greater than 1 and less equals to 5 print ( "\nThere is not any Non-Fibonacci series that lies between 1 to " , no, " term of Fibonacci Series." ) else : # If range is greater than 5 for m in range ( 2 , no): # Loop to calculate fibonacci series till range k = i + j i = j j = k b.append(k) # Store fibonacci series into list b i = 5 print ( "\nThe Non-Fibonacci series that lies between 1 to " , no, " term of Fibonacci Series is:" ) for ans in range ( 4 , b[no - 1 ]): # Loop to calculate Non-Fibonacci series if ans ! = b[i]: print (ans, end = " " ) # Print Non-Fibonacci Series else : i = i + 1 |
C#
// C# code to implement the approach using System; class GFG { public static void Main( string [] args) { int [] holes = { 21, 3, 6 }; int i = 0, j = 1, k, m, no = 10; int [] b = new int [10]; // Range is 10 b[1] = 0; b[2] = 1; // Check if range is less equals to 1 if (no <= 1) { Console.Write( "You have enter a wrong range" ); } // check if range is greater than 1 // and less equals to 5 else if (no <= 5 && no > 1) { Console.Write( "\n" + "There is not any Non-Fibonacci series that lies between 1 to" + no + " term of Fibonacci Series." ); } // If range is greater than 5 else { // Loop to calculate fibonacci series till // range for (m = 2; m < no; m++) { k = i + j; i = j; j = k; // Store fibonacci series into b[] // array b[m] = k; } i = 5; Console.WriteLine( "\n" + "The Non-Fibonacci series that lies between 1 to " + no + " term of Fibonacci Series is: " ); // Loop to calculate Non-Fibonacci // series for ( int ans = 4; ans < b[no - 1]; ans++) { if (ans != b[i]) // Print Non-Fibonacci Series Console.Write(ans + " " ); else i++; } } } } // This Solution is contributed by phasing17 |
Javascript
<script> // driver code let i = 0, j = 1, k, m, no, b = new Array(10); // Range is 10 no = 10; b[1] = 0; b[2] = 1; // Check if range is less equals to 1 if (no <= 1) { console.log( "You have enter a wrong range" ); } // check if range is greater than 1 // and less equals to 5 else if (no <= 5 && no > 1) { document.write( "</br>" , "There is not any Non-Fibonacci series that lies between 1 to " + no + " term of Fibonacci Series." ); } // If range is greater than 5 else { // Loop to calculate fibonacci series till // range for (m = 2; m < no; m++) { k = i + j; i = j; j = k; // Store fibonacci series into b[] // array b[m] = k; } i = 5; document.write( "</br>" , "The Non-Fibonacci series that lies between 1 to " + no + " term of Fibonacci Series is: " , "</br>" ); // Loop to calculate Non-Fibonacci // series for (let ans = 4; ans < b[no - 1]; ans++) { if (ans != b[i]) // Print Non-Fibonacci Series document.write(ans , " " ); else i++; } } // This code is contributed by shinjanpatra </script> |
Output
The Non-Fibonacci series that lies between 1 to 10 term of Fibonacci Series is: 4 6 7 9 10 11 12 14 15 16 17 18 19 20 22 23 24 25 26 27 28 29 30 31 32 33
Time Complexity : O(n) , Auxiliary Space : O(n)
The above problem and solution are contributed by Hemang Sarkar.