Sum and Product of K Smallest and Largest Fibonacci Numbers in the Array

Solution Approach

Approach 1: Solution using a vector

There is a formula named Binet's formula, according to which a number n is a Fibonacci number if and only if one or both of (5*(n)^2 + 4) or (5*(n)^2 – 4) is a perfect square. 

So, in this approach, we'll store all the Fibonacci numbers in a vector. Sort the vector. Then, from the vector, we'll select the K smallest numbers, find their sum and product, and print it. Similarly, we'll select the K largest numbers, find their sum and product, and print it. 

The query you must be having right now is how will we check if a number, n, is a Fibonacci number. So, for this, we'll use the above formula's conclusion and check if one or both of (5*(n)^2 + 4) or (5*(n)^2 – 4) is a perfect square. If yes, the number is a Fibonacci number, otherwise not.

Steps are:

• Input the values of n, the array a, and K.
   
• Declare a vector, fibonacci_numbers, which stores all the Fibonacci numbers present in the array
   
• Traverse each number of the array one by one. If the current number is a Fibonacci number, push it into the fibonacci_numbers vector.
   
• Sort the Fibonacci numbers vector so that it's easy to find the K smallest and the K largest Fibonacci numbers
   
• Declare and initialize two variables. Sum1 and product1. Sum1 will contain the sum of K smallest Fibonacci numbers, and product1 will contain the product of K smallest Fibonacci numbers. Initialize sum1 to 0 and product1 to 1
   
• Since the vector fibonacci_numbers is sorted, the first K numbers in that vector will be the K smallest Fibonacci numbers. To traverse them and calculate their sum and product. For calculating the sum, keep adding them in sum1, and for calculating the product, keep multiplying them with product1.
   
• Print the values of sum1 and product1
   
• Similarly, for K largest Fibonacci numbers, Declare and initialize two variables. Sum2 and product2. Sum2 will contain the sum of K largest Fibonacci numbers, and product2 will contain the product of K largest Fibonacci numbers. Initialize sum2 to 0 and product2 to 1.
   
• Since the vector fibonacci_numbers is sorted, the last K numbers in that vector will be the K largest Fibonacci numbers. To traverse them and calculate their sum and product. For calculating the sum, keep adding them in sum2, and for calculating the product, keep multiplying them with product2.
   
• Print the values of sum2 and product2.

For checking if a number is a Fibonacci number, we're calling out a function named Fibonacci with the number n as the parameter. The steps of implementation of this function are:

• Return if (5*n^2+4) or (5*n^2-4) is a perfect square. 
• For checking if a number x is a perfect square, we're calling the function PerfectSquare. We know that a number x is a perfect square if the square of its integral square root is equal to x. So, we check this in the function and return true if yes. Otherwise, false.
   

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
// Returns true if x is a perfect square, else false
bool PerfectSquare(int x)
{
   // A number x, is a perfect square if the square of its integral 
   //square root is equal to x
   int s = sqrt(x);
   return (s*s == x);
}

// Returns true if n is a Fibonacci Number, else false
bool Fibonacci(int n)
{
   // n is Fibonacci if one or both of 5*n*n + 4 or 5*n*n - 4
   // is a perfect square
   return PerfectSquare(5*n*n + 4) ||
          PerfectSquare(5*n*n - 4);
}
int main()
{
   int n;
   cin>>n; // Input the number of numbers in the array
   int a[n]; 
   for(int i=0;i<n;i++){
       cin>>a[i]; // Input the array
   }
   int K;
   cin>>K; // Input the value of k
   vector<int>fibonacci_numbers; // Declare a vector, fibonacci_numbers, which 
   //stores all the fibonacci numbers present in the array
   for(int i=0;i<n;i++){ // Traverse each number of the array one by one.
       if(Fibonacci(a[i])){  // If the current number is a fibonacci number, 
           // push it into the fibonacci_numbers vector.
           fibonacci_numbers.push_back(a[i]);
       }
   }
   // Sort the fibonacci numbers vector so that it's easy 
   //to find the K smallest and the K largest fibonacci numbers
   sort(fibonacci_numbers.begin(),fibonacci_numbers.end());
   // Declare and initialize two variables. Sum1 and product1. Sum1 will contain 
   //the sum of K smallest fibonacci numbers and product1 will contain the  //product of K smallest fibonacci numbers. Initialize sum1 to 0 and product1 to 1.
   int sum1=0;
   int product1=1;
   // Since the vector fibonacci_numbers is sorted, the first K numbers in that 
   //vector will be the K smallest fibonacci numbers. So traverse them and 
   //calculate their sum and product. For calculating the sum, keep adding them  //in sum1 and for calculating the product, keep multiplying them with product1
   for(int i=0;i<K;i++){
       sum1+=fibonacci_numbers[i];
       product1*=fibonacci_numbers[i];
   }
   //Print the values of sum1 and product1
   cout<<"Sum of K smallest Fibonacci numbers is: "<<sum1<<endl;
   cout<<"Product of K smallest Fibonacci numbers is: "<<product1<<endl;
   //Similarly, for K largest fibonacci numbers. 
   // Declare and initialize two variables. Sum12 and product2. Sum2 will contain 
   //the sum of K largest fibonacci numbers and product2 will contain the product 
   //of K largest fibonacci numbers. Initialize sum2 to 0 and product2 to 1.
   int sum2=0;
   int product2=1;
   int y = fibonacci_numbers.size();
   // Since the vector fibonacci_numbers is sorted, the last K numbers of that 
   //vector will be the K largest fibonacci numbers. So traverse them and 
   //calculate their sum and product. For calculating the sum, keep adding them  //in sum2 and for calculating the product, keep multiplying them with product2.
   for(int i=y-1;i>=y-K;i--){
       sum2+=fibonacci_numbers[i];
       product2*=fibonacci_numbers[i];
   }
   // Print the values of sum2 and product2
   cout<<"Sum of K largest Fibonacci numbers is: "<<sum2<<endl;
   cout<<"Product of K largest Fibonacci numbers is: "<<product2<<endl;
   return 0;
}

Input

8 //n
0 4 3 7 5 18 21 16 // array
3 //K

Output

Sum of K smallest Fibonacci numbers is: 8
Product of K smallest Fibonacci numbers is: 0
Sum of K largest Fibonacci numbers is: 29
Product of K largest Fibonacci numbers is: 315

Complexities

Time complexity

O(nlogn), where n is the number of elements in the array.

Reason: Checking if a number is Fibonacci requires O(1) time. We're doing it for n numbers. So the time taken is O(n). Then, for sorting the Fibonacci numbers, it takes O(nlogn) time in the worst case. For finding out the sum and product then, it takes O(K) time. Thus, the overall complexity is O(nlogn).

Space complexity

O(n), where n is the number of elements in the array.

Reason: We're storing the Fibonacci numbers in the vector, which takes O(n) space in the worst case. And the variables sum1, product1, sum2, and product2 take O(1) space. Thus, the overall space complexity is O(n).

Approach 2: Solution using two priority queues

Another approach for checking if a number is a Fibonacci number or not can be done using hashing (here, an unordered map is used for hashing). What we will do is first find the maximum element of the array. Then, we precalculate all the Fibonacci numbers till that maximum element and store them in a hash table by updating the value of the hash of these calculated Fibonacci numbers to 1. This will help in checking if the number of the array is Fibonacci or not. 

After this, we will declare two heaps(priority queues). One max heap and another min-heap. 

Then, we traverse the array of elements one by one. If the current element is a Fibonacci number, i.e., if the hash value of it is equal to 1, then we push it into both the heaps. After we're done traversing the whole array, the min-heap will contain all the Fibonacci numbers in increasing order, and the max heap will contain all the Fibonacci numbers in decreasing order. So, the top K elements of the min-heap will be the K smallest Fibonacci numbers, and the top K elements of the max heap will be the K largest Fibonacci numbers. Thus, we keep popping out the top K elements from the heaps and keep calculating their sum and product.

Steps are:

• Input the values of n, the array a, and K.
   
• Find the maximum element of the array.
   
• Declare the unordered_map, which will be used to map the values of the Fibonacci numbers to 1
   
• Precompute all the Fibonacci numbers less than or equal to the maximum number of the array and update their map value to 1.
   
• Declare both the heaps i.e. max heap and min-heap.
   
• Traverse each number of the array one by one. If the current number is a Fibonacci number, push it into both the heaps.
   
• Declare and initialize two variables. Sum1 and product1. Sum1 will contain the sum of K smallest Fibonacci numbers, and product1 will contain the product of K smallest Fibonacci numbers. Initialize sum1 to 0 and product1 to 1
   
• Similarly, for K largest Fibonacci numbers, declare and initialize two variables. Sum2 and product2. Sum2 will contain the sum of K largest Fibonacci numbers, and product2 will contain the product of K's largest Fibonacci numbers. Initialize sum2 to 0 and product2 to 1.
   
• The first K numbers in the min-heap will be the K smallest Fibonacci numbers. So keep popping out the top k numbers from the min-heap calculate their sum and product. For calculating the sum, keep adding the popped elements in sum1, and for calculating the product, keep multiplying them with product1.
   
• Similarly, the first K numbers in the max heap will be the K largest Fibonacci numbers. So keep popping out the top k numbers from the max heap to calculate their sum and product. For calculating the sum, keep adding the popped elements in sum2, and for calculating the product, keep multiplying them with product2.
   
• Run a while loop for K times. For each iteration, pop out the top element of the min and max heap. Add and multiply them to their respective sum and product values.
   
• Print the values of sum1, product1, sum2, and product2.

For checking if a number is a Fibonacci number -

The steps are:

• In the unordered map, we're updating the map values of all the Fibonacci numbers less than or equal to the maximum element of the array to 1. 
   
• Also, for finding out all the Fibonacci numbers, we're using the fact that Fibonacci numbers are a sequence of numbers in which every number is the sum of the previous and second previous element. Also, the first two numbers are 0 and 1.
   
• Thus, for a number x, if map[x] == 1, this clearly means that a number is a Fibonacci number. 
   

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
void precompute_hash(unordered_map<int,int>&mp,int maximum){
   //the first two numbers of the fibonacci seq are 0 and 1.
   int second_prev=0; 
   int prev=1;
   // First, update the map value of 0 and 1 to 1.
   mp[second_prev] = 1;
   mp[prev] = 1;
   // Then, keep calculating the further fibonacci numbers and keep updating 
   //their map values to 1.
   while(prev<=maximum){
       // The current fibonacci number will be the sum of previous
       // and second previous number
       int current=  prev+second_prev;
       mp[current] = 1;
       // For the next fibonacci number, previous element will be the current 
       //element and the second previous will be the current previous number
       second_prev = prev;
       prev=current;
   }
}
int main()
{
   int n;
   cin>>n; // Input the number of numbers in the array
   
   int a[n]; 
   for(int i=0;i<n;i++)
   {
       cin>>a[i]; // Input the array
   }
   
   int K;
   cin>>K; // Input the value of k
   
   int maximum = *max_element(a,a+n); // Find the maximum element 
   //of the array.
   unordered_map<int,int>mp; // Declare the unordered_map which will
   // be used map the values of the fibonacci numbers to 1.
   
   precompute_hash(mp,maximum); // Precompute all the fibonacci numbers and
   //update their map value to 1.
   
   // Declare both the heaps
   priority_queue<int>max_heap; 
   priority_queue<int,vector<int>,greater<int>>min_heap;
   
   for(int i=0;i<n;i++)
   { 	// Traverse each number of the array one by one.
       if(mp[a[i]]==1)
       {  	// If the current number is a fibonacci number, 
           // push it into both the heaps.
           max_heap.push(a[i]);
           min_heap.push(a[i]);
       }
   }
   // Declare and initialize two variables. Sum1 and product1. Sum1 will contain 
   //the sum of K smallest fibonacci numbers and product1 will contain the product 
   //of K smallest fibonacci numbers. Initialize sum1 to 0 and product1 to 1.
   
   int sum1=0;
   int product1=1;
   
   //Similarly, for K largest fibonacci numbers. 
   // Declare and initialize two variables. Sum12 and product2. Sum2 will contain 
   //the sum of K largest fibonacci numbers and product2 will contain the product 
   //of K largest fibonacci numbers. Initialize sum2 to 0 and product2 to 1.
   
   int sum2=0;
   int product2=1;
   
   // The first K numbers in the min heap will be the K smallest fibonacci numbers. 
   //So keep popping out the top k numbers from the min heap calculate their sum 
   //and product. For calculating the sum, keep adding the popped elements in 
   //sum1 and for calculating the product, keep multiplying them with product1.
   // Similarly, the first K numbers in the max heap will be the K largest fibonacci numbers. 
   //So keep popping out the top k numbers from the max heap calculate their sum 
   //and product. For calculating the sum, keep adding the popped elements in 
   //sum2 and for calculating the product, keep multiplying them with product2.
   
   while(K--)
   {
       // Pop out the top element of the min and max heap. 
       // Add and multiply them to their respective sum and product values
       
       int mn = min_heap.top();
       min_heap.pop();
       int mx = max_heap.top();
       max_heap.pop();
       
       sum1+=mn;
       product1*=mn;
       
       sum2+=mx;
       product2*=mx;
   }
   //Print the values of sum1 and product1
   cout<<"Sum of K smallest Fibonacci numbers is: "<<sum1<<endl;
   cout<<"Product of K smallest Fibonacci numbers is: "<<product1<<endl;
   
   // Print the values of sum2 and product2
   cout<<"Sum of K largest Fibonacci numbers is: "<<sum2<<endl;
   cout<<"Product of K largest Fibonacci numbers is: "<<product2<<endl;
   
   return 0;
}

Input

8 //n
0 4 3 7 5 18 21 16 // array
3 //K

Output

Sum of K smallest Fibonacci numbers is: 8
Product of K smallest Fibonacci numbers is: 0
Sum of K largest Fibonacci numbers is: 29
Product of K largest Fibonacci numbers is: 315

Complexities

Time complexity

O(nlogn), where n is the number of elements in the array.

Reason: Checking if a number is Fibonacci requires O(1) time. We're doing it for n numbers. So the time taken is O(n). For finding out the sum and product then, we're running a while loop for K times in which each iteration takes O(logn) time in the worst case due to the priority queue operations. So, for the while loop, the total time complexity is O(k*logn). In the worst case, k can be equal to n. Thus, the overall complexity is O(nlogn).

Space complexity

O(n), where n is the number of elements in the array.

Reason: We're storing the Fibonacci numbers in the priority queue, which takes O(n) space in the worst case. Also, we have used an unordered map to precalculate the Fibonacci numbers which also take O(N) space, where N is the maximum number present in the array.
And the variables sum1, product1, sum2, and product2 take O(1) space. Thus, the overall space complexity is O(n).

Check out this problem - Two Sum Problem

Frequently Asked Questions

What are Fibonacci numbers?

In mathematics, the Fibonacci numbers are a sequence of numbers, starting with 0,1, such that each number in the sequence is the sum of the last two numbers of the sequence.

What is a priority queue?

A priority queue is a data structure in which elements have a priority associated with them and are arranged according to their priority order.

What are the types of priority queues?

There are two major types of priority queues, namely, min-heap and max-heap.

What is a min-heap?

Min heap is a type of priority queue data structure or a type of binary heap in which elements are arranged in increasing order of their value. In this heap, the root is always lesser than the children.

What is max-heap?

Max heap is a type of priority queue data structure or a type of binary heap in which elements are arranged in decreasing order of their value. In this heap, the root is always greater than the children.

What is an unordered map, and how is it used for hashing?

An unordered map is a data structure that stores key-value pairs in it, and therefore, it is used to implement hash tables. We can map the value across their keys using an unordered map.

Conclusion

In this article, we solved the problem of finding the sum and product of K's smallest and largest Fibonacci numbers in an array. We discussed two approaches. One involves vectors, and the other involves maps and priority queues. This problem required the knowledge of Fibonacci numbers. Similar problems involving Fibonacci numbers are n-th Fibonacci number, Fibonacci sum, the nth element of modified Fibonacci series, split array into a Fibonacci sequence, and ninja and Fibonacci numbers. You can solve these to gain expertise in this topic. Also, check out some of the popular Practice Problems.

Want to explore more? Check out the following blogs:

• Lexicographically Largest String using at most K Swaps at Same Parity Indices
• Kth smallest element in a row-wise and column-wise sorted 2D array
• The maximum sum of two non-overlapping intervals in a list of Intervals | Interval Scheduling Problem
• Find The Minimum Range Size That Contains The Given Element for Q Queries
   

To practice more such problems, Coding Ninjas Studio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies by providing Online Mock Test Series and many more such benefits.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!