Given a number N, the task is to find the count of Fibonacci pairs in range 0 to N whose sum is N.
Examples:
Input: N = 90
Output: 1
Explanation:
Only Fibonacci pair in range [0, 90] whose sum is equal to 90 is {1, 89}Input: N = 3
Output: 2
Explanation:
Fibonacci Pair in range [0, 3] with whose sum is equal to 3 are {0, 3}, {1, 2}
Approach:
- The idea is to use hashing to precompute and store the Fibonacci numbers less than equal to N in a hash
- Initialize a counter variable as 0
- Then for each element K in that hash, check if N – K is also present in the hash.
- If both K and N – K are in hash, increment the counter variable
Below is the implementation of the above approach:
C++
// C++ program to find count of// Fibonacci pairs 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 count of Fibonacci// pair with the given sumint findFibonacciPairCount(int N){ // creating a set containing // all fibonacci numbers set<int> hash; createHash(hash, N); // Initialize count with 0 int count = 0; // traverse the hash to find // pairs with sum as N set<int>::iterator itr; for (itr = hash.begin(); *itr <= (N / 2); itr++) { // If both *itr and //(N - *itr) are Fibonacci // increment the count if (hash.find(N - *itr) != hash.end()) { // Increase the count count++; } } // Return the count return count;}// Driven codeint main(){ int N = 90; cout << findFibonacciPairCount(N) << endl; N = 3; cout << findFibonacciPairCount(N) << endl; return 0;} |
Java
// Java program to find count of// Fibonacci pairs whose// sum can be represented as Nimport java.util.*;class GFG{ // Function to create hash table// to check Fibonacci numbersstatic 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 count of Fibonacci// pair with the given sumstatic int findFibonacciPairCount(int N){ // creating a set containing // all fibonacci numbers HashSet<Integer> hash = new HashSet<Integer>(); createHash(hash, N); // Initialize count with 0 int count = 0; int i = 0; // traverse the hash to find // pairs with sum as N for (int itr : hash) { i++; // If both *itr and //(N - *itr) are Fibonacci // increment the count if (hash.contains(N - itr)) { // Increase the count count++; } if(i == hash.size()/2) break; } // Return the count return count;} // Driven codepublic static void main(String[] args){ int N = 90; System.out.print(findFibonacciPairCount(N) +"\n"); N = 3; System.out.print(findFibonacciPairCount(N) +"\n"); }}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find count of # Fibonacci pairs whose sum can be# represented as N # Function to create hash table # to check Fibonacci numbers def createHash(Hash, maxElement): # Storing the first two numbers # in the hash prev, curr = 0, 1 Hash.add(prev) Hash.add(curr) # Finding Fibonacci numbers up to N # and storing them in the hash while (curr < maxElement): temp = curr + prev Hash.add(temp) prev = curr curr = temp # Function to find count of Fibonacci # pair with the given sum def findFibonacciPairCount(N): # Creating a set containing # all fibonacci numbers Hash = set() createHash(Hash, N) # Initialize count with 0 count = 0 i = 0 # Traverse the hash to find # pairs with sum as N for itr in Hash: i += 1 # If both *itr and #(N - *itr) are Fibonacci # increment the count if ((N - itr) in Hash): # Increase the count count += 1 if (i == (len(Hash) // 2)): break # Return the count return count # Driver CodeN = 90print(findFibonacciPairCount(N)) N = 3print(findFibonacciPairCount(N)) # This code is contributed by divyeshrabadiya07 |
C#
// C# program to find count of// Fibonacci pairs whose// sum can be represented as Nusing System;using System.Collections.Generic;class GFG{ // Function to create hash table// to check Fibonacci numbersstatic 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 count of Fibonacci// pair with the given sumstatic int findFibonacciPairCount(int N){ // creating a set containing // all fibonacci numbers HashSet<int> hash = new HashSet<int>(); createHash(hash, N); // Initialize count with 0 int count = 0; int i = 0; // traverse the hash to find // pairs with sum as N foreach (int itr in hash) { i++; // If both *itr and //(N - *itr) are Fibonacci // increment the count if (hash.Contains(N - itr)) { // Increase the count count++; } if(i == hash.Count/2) break; } // Return the count return count;} // Driven codepublic static void Main(String[] args){ int N = 90; Console.Write(findFibonacciPairCount(N) +"\n"); N = 3; Console.Write(findFibonacciPairCount(N) +"\n"); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find count of// Fibonacci pairs 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 var 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) { var temp = curr + prev; hash.add(temp); prev = curr; curr = temp; }}// Function to find count of Fibonacci// pair with the given sumfunction findFibonacciPairCount(N){ // creating a set containing // all fibonacci numbers var hash = new Set(); createHash(hash, N); // Initialize count with 0 var count = 0, i =0; // traverse the hash to find // pairs with sum as N hash.forEach(element => { i++; if(hash.size >= parseInt(i*2)) { // If both *itr and //(N - *itr) are Fibonacci // increment the count if (hash.has(N-element)) { // Increase the count count++; } } }); // Return the count return count;}// Driven codevar N = 90;document.write( findFibonacciPairCount(N) + "<br>")N = 3;document.write( findFibonacciPairCount(N) + "<br>")// This code is contributed by rrrtnx.</script> |
Output:
1 2
Performance Analysis:
- Time Complexity: In the above approach, building hashmap of fibonacci numbers less than N would be O(N) operation. Then, for each element in hashmap, we search for another element making the search time complexity to be O(N * log N). So overall time complexity is O(N * log N)
- Auxiliary Space Complexity: In the above approach, we are using extra space for storing hashmap values. So Auxiliary space complexity is 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!
