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 numbersvoid 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 sumvoid 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 codeint 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 numbersdef 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 sumdef 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 codeif __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 numbersfunction 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 sumfunction 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
