Find two Fibonacci numbers whose sum can be represented as N
Given an even number N, the task is to find two Fibonacci numbers whose sum can be represented as N. There may be several combinations possible. Print only first such pair. If there is no solution then print -1.
Examples:
Input: N = 90
Output: 1, 89
Explanation:
The first pair with whose sum is equal to 90 is {1, 89}
Input: N = 74
Output: -1
Approach: The idea is to use hashing to precompute and store the Fibonacci numbers, and then check if a pair is a Fibonacci value in O(1) time.
Below is the implementation of the above approach:
CPP
// C++ program to find two // Fibonacci numbers whose // sum can be represented as N #include <bits/stdc++.h> using namespace std; // Function to create hash table // to check Fibonacci numbers void createHash(set< int >& hash, int maxElement) { // Storing the first two numbers // in the hash int prev = 0, curr = 1; hash.insert(prev); hash.insert(curr); // Finding Fibonacci numbers up to N // and storing them in the hash while (curr < maxElement) { int temp = curr + prev; hash.insert(temp); prev = curr; curr = temp; } } // Function to find the Fibonacci pair // with the given sum void findFibonacciPair( int n) { // creating a set containing // all fibonacci numbers set< int > hash; createHash(hash, n); // Traversing all numbers // to find first pair for ( int i = 0; i < n; i++) { // If both i and (N - i) are Fibonacci if (hash.find(i) != hash.end() && hash.find(n - i) != hash.end()) { // Printing the pair because // i + (N - i) = N cout << i << ", " << (n - i) << endl; return ; } } // If no fibonacci pair is found // whose sum is equal to n cout << "-1\n" ; } // Driven code int main() { int N = 90; findFibonacciPair(N); return 0; } |
Java
// Java program to find two // Fibonacci numbers whose // sum can be represented as N import java.util.*; class GFG{ // Function to create hash table // to check Fibonacci numbers static void createHash(HashSet<Integer> hash, int maxElement) { // Storing the first two numbers // in the hash int prev = 0 , curr = 1 ; hash.add(prev); hash.add(curr); // Finding Fibonacci numbers up to N // and storing them in the hash while (curr < maxElement) { int temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to find the Fibonacci pair // with the given sum static void findFibonacciPair( int n) { // creating a set containing // all fibonacci numbers HashSet<Integer> hash = new HashSet<Integer>(); createHash(hash, n); // Traversing all numbers // to find first pair for ( int i = 0 ; i < n; i++) { // If both i and (N - i) are Fibonacci if (hash.contains(i) && hash.contains(n - i)) { // Printing the pair because // i + (N - i) = N System.out.print(i+ ", " + (n - i) + "\n" ); return ; } } // If no fibonacci pair is found // whose sum is equal to n System.out.print( "-1\n" ); } // Driven code public static void main(String[] args) { int N = 90 ; findFibonacciPair(N); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find two # Fibonacci numbers whose # sum can be represented as N # Function to create hash table # to check Fibonacci numbers def createHash(hash1,maxElement): # Storing the first two numbers # in the hash prev , curr = 0 , 1 hash1.add(prev) hash1.add(curr) # Finding Fibonacci numbers up to N # and storing them in the hash while (curr < maxElement): temp = curr + prev hash1.add(temp) prev = curr curr = temp # Function to find the Fibonacci pair # with the given sum def findFibonacciPair( n): # creating a set containing # all fibonacci numbers hash1 = set () createHash(hash1, n) # Traversing all numbers # to find first pair for i in range (n): # If both i and (N - i) are Fibonacci if (i in hash1 and (n - i) in hash1): # Printing the pair because # i + (N - i) = N print (i , ", " , (n - i)) return # If no fibonacci pair is found # whose sum is equal to n print ( "-1" ) # Driven code if __name__ = = "__main__" : N = 90 findFibonacciPair(N) # This code is contributed by chitranayal |
C#
// C# program to find two // Fibonacci numbers whose // sum can be represented as N using System; using System.Collections.Generic; class GFG{ // Function to create hash table // to check Fibonacci numbers static void createHash(HashSet< int > hash, int maxElement) { // Storing the first two numbers // in the hash int prev = 0, curr = 1; hash.Add(prev); hash.Add(curr); // Finding Fibonacci numbers up to N // and storing them in the hash while (curr < maxElement) { int temp = curr + prev; hash.Add(temp); prev = curr; curr = temp; } } // Function to find the Fibonacci pair // with the given sum static void findFibonacciPair( int n) { // creating a set containing // all fibonacci numbers HashSet< int > hash = new HashSet< int >(); createHash(hash, n); // Traversing all numbers // to find first pair for ( int i = 0; i < n; i++) { // If both i and (N - i) are Fibonacci if (hash.Contains(i) && hash.Contains(n - i)) { // Printing the pair because // i + (N - i) = N Console.Write(i+ ", " + (n - i) + "\n" ); return ; } } // If no fibonacci pair is found // whose sum is equal to n Console.Write( "-1\n" ); } // Driven code public static void Main(String[] args) { int N = 90; findFibonacciPair(N); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to find two // Fibonacci numbers whose // sum can be represented as N // Function to create hash table // to check Fibonacci numbers function createHash(hash, maxElement) { // Storing the first two numbers // in the hash let prev = 0, curr = 1; hash.add(prev); hash.add(curr); // Finding Fibonacci numbers up to N // and storing them in the hash while (curr < maxElement) { let temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to find the Fibonacci pair // with the given sum function findFibonacciPair(n) { // creating a set containing // all fibonacci numbers let hash = new Set(); createHash(hash, n); // Traversing all numbers // to find first pair for (let i = 0; i < n; i++) { // If both i and (N - i) are Fibonacci if (hash.has(i) && hash.has(n - i)) { // Printing the pair because // i + (N - i) = N document.write(i+ ", " + (n - i) + "<br/>" ); return ; } } // If no fibonacci pair is found // whose sum is equal to n document.write( "-1" + "<br/>" ); } // Driver code let N = 90; findFibonacciPair(N); // This code is contributed by sanjoy_62. </script> |
Output:
1, 89
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us