Dado un entero K y una array arr[] que contiene N enteros, la tarea es encontrar la suma y el producto de los K números de Fibonacci más pequeños y los K más grandes en la array.
Nota: suponga que hay al menos K números de Fibonacci en la array.
Ejemplos:
Entrada: arr[] = {2, 5, 6, 8, 10, 11}, K = 2
Salida: La
suma de los K números de Fibonacci mínimos es 7
El producto de los K números de Fibonacci mínimos es 10
La suma de los K números de Fibonacci máximos es 13
El producto de los números de Fibonacci máximos K es 40
Explicación:
{2, 5, 8} son los únicos números de Fibonacci de la array.
{2, 5} son los 2 más pequeños y {5, 8} son los 2 más grandes entre ellos.Entrada: arr[] = {3, 2, 12, 13, 5, 19}, K = 3
Salida: La
suma de los K números de Fibonacci mínimos es 10
El producto de los K números de Fibonacci mínimos es 30
La suma de los K números de Fibonacci máximos es 21
El producto de K-números máximos de Fibonacci es 195
Enfoque: La idea es usar hashing para precalcular y almacenar los Nodes de Fibonacci hasta el valor máximo, en un Set , para que la verificación sea fácil y eficiente (en tiempo O(1)).
- Recorra toda la array y obtenga el valor máximo en la lista.
- Ahora, cree una tabla hash que contenga todos los Nodes de Fibonacci menores o iguales al valor máximo de la array.
Después de realizar el cálculo previo anterior, recorra la array e inserte todos los números que son Fibonacci en dos montones , un montón mínimo y un montón máximo .
Ahora, extraiga los elementos K superiores del montón mínimo y máximo para calcular la suma y el producto de los números K de Fibonacci.
A continuación se muestra la implementación del enfoque anterior:
// C++ program to find the sum and
// product of K smallest and K
// largest Fibonacci numbers in an array
#include <bits/stdc++.h>
using namespace std;
// Function to create the hash table
// to check Fibonacci numbers
void createHash(set<int>& hash,
int maxElement)
{
// Inserting the first two elements
// into the hash
int prev = 0, curr = 1;
hash.insert(prev);
hash.insert(curr);
// Computing the remaining
// elements using
// the previous two elements
while (curr <= maxElement) {
int temp = curr + prev;
hash.insert(temp);
prev = curr;
curr = temp;
}
}
// Function that calculates the sum
// and the product of K smallest and
// K largest Fibonacci numbers in an array
void fibSumAndProduct(int arr[],
int n, int k)
{
// Find the maximum value in the array
int max_val = *max_element(arr, arr + n);
// Creating a hash containing
// all the Fibonacci numbers
// upto the maximum data value
// in the array
set<int> hash;
createHash(hash, max_val);
// Max Heap to store all the
// Fibonacci numbers
priority_queue<int> maxHeap;
// Min Heap to store all the
// Fibonacci numbers
priority_queue<int,
vector<int>,
greater<int> >
minHeap;
// Push all the fibonacci numbers
// from the array to the heaps
for (int i = 0; i < n; i++)
if (hash.find(arr[i])
!= hash.end()) {
minHeap.push(arr[i]);
maxHeap.push(arr[i]);
}
long long int minProduct = 1,
maxProduct = 1,
minSum = 0,
maxSum = 0;
// Finding the K minimum
// and the K maximum
// elements from the heaps
while (k--) {
// Calculate the products
minProduct *= minHeap.top();
maxProduct *= maxHeap.top();
// Calculate the sum
minSum += minHeap.top();
maxSum += maxHeap.top();
// Pop the current
// minimum element
minHeap.pop();
// Pop the current
// maximum element
maxHeap.pop();
}
cout << "Sum of K-minimum "
<< "fibonacci numbers is "
<< minSum << "\n";
cout << "Product of K-minimum "
<< "fibonacci numbers is "
<< minProduct << "\n";
cout << "Sum of K-maximum "
<< "fibonacci numbers is "
<< maxSum << "\n";
cout << "Product of K-maximum "
<< "fibonacci numbers is "
<< maxProduct;
}
// Driver code
int main()
{
int arr[] = { 2, 5, 6, 8, 10, 11 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
fibSumAndProduct(arr, N, K);
return 0;
}
Sum of K-minimum fibonacci numbers is 7 Product of K-minimum fibonacci numbers is 10 Sum of K-maximum fibonacci numbers is 13 Product of K-maximum fibonacci numbers is 40
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA