# Sum and product of K smallest and largest Fibonacci numbers in the array

## Introduction

In mathematics, the __Fibonacci numbers__ are a sequence of numbers such that each number in the sequence is the sum of the last two numbers of the sequence. This sequence starts with the numbers 0 and 1. Thus the sequence is, 0,1,1,2,3,5,8,13,.... In this article, we'll see how to find the sum and product of K smallest and largest Fibonacci numbers in a given array.

## Problem Statement

You are given an array, a, of n integers. Find both the sum and product of K smallest and largest Fibonacci numbers in the array.

**Note**: It is guaranteed that the array contains at least K Fibonacci numbers.

**For example,**

**Input**: n = 8, a = [0,4,3,7,5,18,16,21], K = 3

**Output**: Sum of K smallest fibonacci numbers = 8

Product of K smallest fibonacci numbers = 0

Sum of K largest fibonacci numbers = 29

Product of K largest fibonacci numbers = 315

**Explanation**: In the given array, numbers [0,3,5,21] are the only Fibonacci numbers. So, the K smallest Fibonacci numbers are [0,3,5], and thus their sum is eight and product is 0. And, the K largest Fibonacci numbers are [3,5,21]. Thus, their sum is 29, and the product is 315.

## 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 that 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 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 **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 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 takes 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)**.

## 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 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.

## Key Takeaways

In this article, we solved the problem of finding the sum and product of K 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.

To practice more such problems, __Codestudio__ 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.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think