Dado un entero k y un arreglo de enteros arr , la tarea es encontrar la suma y el producto de los k números compuestos más pequeños y los k más grandes en el arreglo.
Suponga que hay al menos k números compuestos en la array.
Ejemplos:
Entrada: arr[] = {2, 5, 6, 8, 10, 11}, k = 2
Salida: La suma de los k números compuestos mínimos es 14
La suma de los k números compuestos máximos es 18
Producto de los k números compuestos mínimos es 48
El producto de k-números compuestos máximos es 80
{6, 8, 10} son los únicos números compuestos de la array. {6, 8} son los 2 más pequeños y {8, 10} son los 2 más grandes entre ellos.
Entrada: arr[] = {6, 4, 2, 12, 13, 5, 19, 10}, k = 3
Salida: La suma de los k números compuestos mínimos es 20
La suma de los k números compuestos máximos es 28
Producto de k -los números compuestos mínimos son 240
El producto de k-los números compuestos máximos son 720
Acercarse:
- El uso de Sieve of Eratosthenes genera un vector booleano hasta el tamaño del elemento máximo de la array que se puede usar para verificar si un número es compuesto o no.
- También establezca 0 y 1 como primos para que no se cuenten como números compuestos.
- Ahora recorra la array e inserte todos los números que están compuestos en dos montones , un montón mínimo y un montón máximo.
- Ahora, saque los k elementos superiores del montón mínimo y tome la suma y el producto de los k números compuestos mínimos .
- Haga lo mismo con el montón máximo para obtener la suma y el producto de los números compuestos máximos k .
- Finalmente, imprima los resultados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum and
// product of k smallest and k largest
// composite numbers in an array
#include <bits/stdc++.h>
using namespace std;
vector<bool> SieveOfEratosthenes(int max_val)
{
// Create a boolean vector "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
vector<bool> prime(max_val + 1, true);
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
return prime;
}
// Function that calculates the sum
// and product of k smallest and k
// largest composite numbers in an array
void compositeSumAndProduct(int arr[], int n, int k)
{
// Find maximum value in the array
int max_val = *max_element(arr, arr + n);
// Use sieve to find all prime numbers
// less than or equal to max_val
vector<bool> prime = SieveOfEratosthenes(max_val);
// Set 0 and 1 as primes so that
// they don't get counted as
// composite numbers
prime[0] = true;
prime[1] = true;
// Max Heap to store all the composite numbers
priority_queue<int> maxHeap;
// Min Heap to store all the composite numbers
priority_queue<int, vector<int>, greater<int>>
minHeap;
// Push all the composite numbers
// from the array to the heaps
for (int i = 0; i < n; i++)
if (!prime[arr[i]]) {
minHeap.push(arr[i]);
maxHeap.push(arr[i]);
}
long long int minProduct = 1
, maxProduct = 1
, minSum = 0
, maxSum = 0;
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 composite numbers is "
<< minSum << "\n";
cout << "Sum of k-maximum composite numbers is "
<< maxSum << "\n";
cout << "Product of k-minimum composite numbers is "
<< minProduct << "\n";
cout << "Product of k-maximum composite numbers is "
<< maxProduct;
}
// Driver code
int main()
{
int arr[] = { 4, 2, 12, 13, 5, 19 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
compositeSumAndProduct(arr, n, k);
return 0;
}
Java
// Java program to find the sum and
// product of k smallest and k largest
// composite numbers in an array
import java.util.*;
class GFG
{
static boolean[] SieveOfEratosThenes(int max_val)
{
// Create a boolean vector "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
boolean[] prime = new boolean[max_val + 1];
Arrays.fill(prime, true);
for (int p = 2; p * p <= max_val; p++)
{
// If prime[p] is not changed, then
// it is a prime
if (prime[p])
{
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
return prime;
}
// Function that calculates the sum
// and product of k smallest and k
// largest composite numbers in an array
static void compositeSumAndProduct(Integer[] arr,
int n, int k)
{
// Find maximum value in the array
int max_val = Collections.max(Arrays.asList(arr));
// Use sieve to find all prime numbers
// less than or equal to max_val
boolean[] prime = SieveOfEratosThenes(max_val);
// Set 0 and 1 as primes so that
// they don't get counted as
// composite numbers
prime[0] = true;
prime[1] = true;
// Max Heap to store all the composite numbers
PriorityQueue<Integer> maxHeap =
new PriorityQueue<Integer>((x, y) -> y - x);
// Min Heap to store all the composite numbers
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Push all the composite numbers
// from the array to the heaps
for (int i = 0; i < n; i++)
{
if (!prime[arr[i]])
{
minHeap.add(arr[i]);
maxHeap.add(arr[i]);
}
}
long minProduct = 1, maxProduct = 1,
minSum = 0, maxSum = 0;
Integer lastMin = 0, lastMax = 0;
while (k-- > 0)
{
if (minHeap.peek() != null ||
maxHeap.peek() != null)
{
// Calculate the products
minProduct *= minHeap.peek();
maxProduct *= maxHeap.peek();
// Calculate the sum
minSum += minHeap.peek();
maxSum += maxHeap.peek();
// Pop the current minimum element
lastMin = minHeap.poll();
// Pop the current maximum element
lastMax = maxHeap.poll();
}
else
{
// when maxHeap or minHeap is exhausted
// then this condition will run
minProduct *= lastMin;
maxProduct *= lastMax;
minSum += lastMin;
maxSum += lastMax;
}
}
System.out.println("Sum of k-minimum composite" +
" numbers is " + minSum);
System.out.println("Sum of k-maximum composite" +
" numbers is " + maxSum);
System.out.println("Product of k-minimum composite" +
" numbers is " + minProduct);
System.out.println("Product of k-maximum composite" +
" numbers is " + maxProduct);
}
// Driver Code
public static void main(String[] args)
{
Integer[] arr = { 4, 2, 12, 13, 5, 19 };
int n = arr.length;
int k = 3;
compositeSumAndProduct(arr, n, k);
}
}
// This code is contributed by
// sanjeev2552
Producción:
Sum of k-minimum composite numbers is 28 Sum of k-maximum composite numbers is 20 Product of k-minimum composite numbers is 576 Product of k-maximum composite numbers is 192
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA