Dado un arreglo arr[] que consta de N enteros y un entero positivo K , la tarea es encontrar el número de subarreglos de tamaño K cuyo promedio es mayor que su mediana y tanto el promedio como la mediana deben ser primos o no primos.
Ejemplos:
Entrada: arr[] = {2, 4, 3, 5, 6}, K = 3
Salida: 2
Explicación:
Los siguientes son los subarreglos que satisfacen las condiciones dadas:
- {2, 4, 3}: la mediana de este subarreglo es 3, y el promedio es (2 + 4 + 3)/3 = 3. Como, tanto la mediana como el promedio son primos y promedio >= mediana. Así que el conteo de este subarreglo.
- {4, 3, 5}: la mediana de este subarreglo es 4, y el promedio es (4 + 3 + 5)/3 = 4. Como, tanto la mediana como el promedio son no primos y promedio >= mediana. Así que el conteo de este subarreglo.
Por lo tanto, el número total de subarreglos es 2.
Entrada: arr[] = {2, 4, 3, 5, 6}, K = 2
Salida: 3
Enfoque: el problema dado se puede resolver utilizando estructuras de datos basadas en políticas , es decir, conjunto_ordenado . Siga los pasos a continuación para resolver el problema dado:
- Precalcule todos los números primos y no primos hasta 10 5 usando Sieve Of Eratosthenes .
- Inicialice una variable, digamos count , que almacena el recuento resultante de subarreglos.
- Encuentre el promedio y la mediana de los primeros K elementos y si el promedio >= mediana y tanto el promedio como las medianas son primos o no primos, entonces incremente el conteo en 1 .
- Almacene los primeros elementos de la array K en el conjunto_ordenado .
- Recorra la array dada en el rango [0, N – K] y realice los siguientes pasos:
- Elimine el elemento actual arr[i] del conjunto_ordenado y agregue (i + k) el elemento, es decir, arr[i + K] al conjunto_ordenado.
- Encuentre la mediana de la array usando la función find_order_by_set((K + 1)/2 – 1) .
- Encuentre el promedio del subarreglo actual .
- Si el promedio >= la mediana y tanto el promedio como las medianas son primos o no primos, incremente el conteo en 1 .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <stdlib.h>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
const int mxN = (int)1e5;
// Stores whether i is prime or not
bool prime[mxN + 1];
// Function to precompute all the prime
// numbers using sieve of eratosthenes
void SieveOfEratosthenes()
{
// Initialize the prime array
memset(prime, true, sizeof(prime));
// Iterate over the range [2, mxN]
for (int p = 2; p * p <= mxN; p++) {
// If the prime[p] is unchanged,
// then it is a prime
if (prime[p]) {
// Mark all multiples of p
// as non-prime
for (int i = p * p;
i <= mxN; i += p)
prime[i] = false;
}
}
}
// Function to find number of subarrays
// that satisfy the given criteria
int countSubarray(int arr[], int n, int k)
{
// Initialize the ordered_set
ordered_set s;
// Stores the sum for subarray
int sum = 0;
for (int i = 0; i < (int)k; i++) {
s.insert(arr[i]);
sum += arr[i];
}
// Stores the average for each
// possible subarray
int avgsum = sum / k;
// Stores the count of subarrays
int ans = 0;
// For finding the median use the
// find_by_order(k) that returns
// an iterator to kth element
int med = *s.find_by_order(
(k + 1) / 2 - 1);
// Check for the valid condition
if (avgsum - med >= 0
&& ((prime[med] == 0
&& prime[avgsum] == 0)
|| (prime[med] != 0
&& prime[avgsum] != 0))) {
// Increment the resultant
// count of subarray
ans++;
}
// Iterate the subarray over the
// the range [0, N - K]
for (int i = 0; i < (int)(n - k); i++) {
// Erase the current element
// arr[i]
s.erase(s.find_by_order(
s.order_of_key(arr[i])));
// The function Order_of_key(k)
// returns the number of items
// that are strictly smaller
// than K
s.insert(arr[i + k]);
sum -= arr[i];
// Add the (i + k)th element
sum += arr[i + k];
// Find the average
avgsum = sum / k;
// Get the median value
med = *s.find_by_order(
(k + 1) / 2 - 1);
// Check the condition
if (avgsum - med >= 0
&& ((prime[med] == 0
&& prime[avgsum] == 0)
|| (prime[med] != 0
&& prime[avgsum] != 0))) {
// Increment the count of
// subarray
ans++;
}
}
// Return the resultant count
// of subarrays
return ans;
}
// Driver Code
int main()
{
// Precompute all the primes
SieveOfEratosthenes();
int arr[] = { 2, 4, 3, 5, 6 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
cout << countSubarray(arr, N, K);
return 0;
}
Producción:
2
Complejidad de tiempo: O(N*log N + N*log(log N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por tejasdeore80 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA