Given an integer N(less than 10^6), the task is to find a pair of Fibonacci numbers whose sum is equal to the given N, and the absolute difference between the chosen pair is minimum.
Print -1 if there is no solution.
Examples:
Input: N = 199
Output: 55 144
Explanation
199 can be represented as sum 55 and 144 which has the minimum difference.
Input: N = 1830
Output: 233 1597
Explanation
1830 can be represented as sum 233 and 1597 which has the minimum difference.
Approach: The idea is to use hashing to precompute and store the Fibonacci nodes up to the maximum value to make checking easy and efficient (in O(1) time).
After precomputing the hash:
- Start a loop from (N / 2) to 1 (to minimize the absolute difference) and check whether the loop counter ‘i’ and ‘N – i’ are both Fibonacci.
- If they are Fibonacci, then we will print them and break out of the loop.
- If the number N cannot be represented as the sum of two Fibonacci numbers, then we will print -1.
Below is the implementation of the above approach:
C++
// C++ program to find the pair of// Fibonacci numbers with a given sum// and minimum absolute difference#include <bits/stdc++.h>using namespace std;#define MAX 1000005// Hash to store all the// Fibonacci numbersset<int> fib;// Function to generate fibonacci Series// and create hash table// to check Fibonacci numbersvoid fibonacci(){ // Adding the first two Fibonacci // numbers into the Hash set int prev = 0, curr = 1, len = 2; fib.insert(prev); fib.insert(curr); // Computing the remaining Fibonacci // numbers based on the previous // two numbers while (len <= MAX) { int temp = curr + prev; fib.insert(temp); prev = curr; curr = temp; len++; }}// Function to find the pair of// Fibonacci numbers with the given// sum and minimum absolute differencevoid findFibonacci(int N){ // Start from N/2 such that the // difference between i and // N - i will be minimum for (int i = N / 2; i > 1; i--) { // If both 'i' and 'sum - i' are // fibonacci numbers then print // them and break the loop if (fib.find(i) != fib.end() && fib.find(N - i) != fib.end()) { cout << i << " " << (N - i) << endl; return; } } // If there is no Fibonacci pair // possible cout << "-1" << endl;}// Driver codeint main(){ // Generate the Fibonacci numbers fibonacci(); int sum = 199; // Find the Fibonacci pair findFibonacci(sum); return 0;} |
Java
// Java program to find the pair of// Fibonacci numbers with a given sum// and minimum absolute differenceimport java.util.*; class GFG{ // Hash to store all the // Fibonacci numbers static int MAX=1000005; static Set<Integer> fib=new HashSet<Integer>(); // Function to generate fibonacci Series // and create hash table // to check Fibonacci numbers static void fibonacci() { // Adding the first two Fibonacci // numbers into the Hash set int prev = 0, curr = 1, len = 2; fib.add(prev); fib.add(curr); // Computing the remaining Fibonacci // numbers based on the previous // two numbers while (len <= MAX) { int temp = curr + prev; fib.add(temp); prev = curr; curr = temp; len++; } } // Function to find the pair of // Fibonacci numbers with the given // sum and minimum absolute difference static void findFibonacci(int N) { // Start from N/2 such that the // difference between i and // N - i will be minimum for (int i = N / 2; i > 1; i--) { // If both 'i' and 'sum - i' are // fibonacci numbers then print // them and break the loop if (fib.contains(i) && fib.contains(N - i)) { System.out.println(i+" "+(N - i)); return; } } // If there is no Fibonacci pair // possible System.out.println("-1"); } // Driver code public static void main(String args[]) { // Generate the Fibonacci numbers fibonacci(); int sum = 199; // Find the Fibonacci pair findFibonacci(sum); }}// This code is contributed by AbhiThakur |
Python3
# Python 3 program to find # the pair of Fibonacci numbers # with a given sum and minimum # absolute differenceMAX = 10005# Hash to store all the# Fibonacci numbersfib = set()# Function to generate # fibonacci Series and # create hash table # to check Fibonacci # numbersdef fibonacci(): global fib global MAX # Adding the first # two Fibonacci numbers # into the Hash set prev = 0 curr = 1 l = 2 fib.add(prev) fib.add(curr) # Computing the remaining # Fibonacci numbers based # on the previous two numbers while(l <= MAX): temp = curr + prev fib.add(temp) prev = curr curr = temp l += 1# Function to find the # pair of Fibonacci numbers # with the given sum and # minimum absolute differencedef findFibonacci(N): global fib # Start from N/2 such # that the difference # between i and N - i # will be minimum i = N//2 while(i > 1): # If both 'i' and 'sum - i' # are fibonacci numbers then # print them and break the loop if (i in fib and (N - i) in fib): print(i, (N - i)) return i -= 1 # If there is no Fibonacci # pair possible print("-1")# Driver codeif __name__ == '__main__': # Generate the Fibonacci # numbers fibonacci() sum = 199 # Find the Fibonacci pair findFibonacci(sum) # This code is contributed by bgangwar59 |
C#
// C# program to find the pair of// Fibonacci numbers with a given sum// and minimum absolute differenceusing System;using System.Collections.Generic;class GFG{ // Hash to store all the // Fibonacci numbers static int MAX=100005; static HashSet<int> fib=new HashSet<int>(); // Function to generate fibonacci Series // and create hash table // to check Fibonacci numbers static void fibonacci() { // Adding the first two Fibonacci // numbers into the Hash set int prev = 0, curr = 1, len = 2; fib.Add(prev); fib.Add(curr); // Computing the remaining Fibonacci // numbers based on the previous // two numbers while (len <= MAX) { int temp = curr + prev; fib.Add(temp); prev = curr; curr = temp; len++; } } // Function to find the pair of // Fibonacci numbers with the given // sum and minimum absolute difference static void findFibonacci(int N) { // Start from N/2 such that the // difference between i and // N - i will be minimum for (int i = N / 2; i > 1; i--) { // If both 'i' and 'sum - i' are // fibonacci numbers then print // them and break the loop if (fib.Contains(i) && fib.Contains(N - i)) { Console.WriteLine(i+" "+(N - i)); return; } } // If there is no Fibonacci pair // possible Console.WriteLine("-1"); } // Driver code public static void Main(String []args) { // Generate the Fibonacci numbers fibonacci(); int sum = 199; // Find the Fibonacci pair findFibonacci(sum); }}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program to find the pair of// Fibonacci numbers with a given sum// and minimum absolute difference // Hash to store all the // Fibonacci numbers let MAX=1000005; let fib=new Set(); // Function to generate fibonacci Series // and create hash table // to check Fibonacci numbers function fibonacci() { // Adding the first two Fibonacci // numbers into the Hash set let prev = 0, curr = 1, len = 2; fib.add(prev); fib.add(curr); // Computing the remaining Fibonacci // numbers based on the previous // two numbers while (len <= MAX) { let temp = curr + prev; fib.add(temp); prev = curr; curr = temp; len++; } } // Function to find the pair of // Fibonacci numbers with the given // sum and minimum absolute difference function findFibonacci(N) { // Start from N/2 such that the // difference between i and // N - i will be minimum for (let i = Math.floor(N / 2); i > 1; i--) { // If both 'i' and 'sum - i' are // fibonacci numbers then print // them and break the loop if (fib.has(i) && fib.has(N - i)) { document.write(i+" "+(N - i)); return; } } // If there is no Fibonacci pair // possible document.write("-1"); }// Driver code // Generate the Fibonacci numbers fibonacci(); let sum = 199; // Find the Fibonacci pair findFibonacci(sum);// This code is contributed by sanjoy_62. </script> |
Output:
55 144
Time Complexity : O(N)
Space Complexity : O(MAX)
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!
