Dada una array arr[] que consta de N enteros positivos. La tarea es encontrar la longitud del subarreglo más largo de este arreglo que contiene exactamente K números primos distintos . Si no existe ningún subarreglo, imprima «-1» .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, K = 1
Salida: 4
Explicación:
El subarreglo {6, 7, 8, 9} contiene 4 elementos y solo uno es primo (7). Por lo tanto, la longitud requerida es 4.Entrada: arr[] = {1, 2, 3, 3, 4, 5, 6, 7, 8, 9}, K = 3
Salida: 8
Explicación:
El subarreglo {3, 3, 4, 5, 6, 7 , 8, 9} contiene 8 elementos y contiene solo 3 primos distintos (3, 5 y 7). Por lo tanto, la longitud requerida es 8.
Enfoque ingenuo: la idea es generar todos los subarreglos posibles y verificar si algún subarreglo con la longitud máxima contiene K números primos distintos. En caso afirmativo, imprima esa longitud del subarreglo; de lo contrario, imprima «-1» .
Complejidad de tiempo: O(N 2 ), donde N es la longitud de la array dada.
Complejidad espacial: O(N)
Enfoque eficiente: la idea es utilizar la criba de Eratóstenes para calcular los números primos y la técnica de dos punteros para resolver el problema anterior. A continuación se muestran los pasos:
- Calcula previamente si el número dado es primo o no usando el tamiz de Eratóstenes .
- Mantenga el conteo de primos que ocurren en la array dada mientras la atraviesa.
- Hasta que K no sea cero, contamos los primos distintivos que ocurren en el subarreglo y disminuimos K en 1.
- A medida que K se vuelve negativo, comience a eliminar los elementos hasta el primer número primo del subarreglo actual, ya que podría haber una posibilidad de un subarreglo más largo después.
- Cuando K es 0 , actualizamos la longitud máxima.
- Imprime la longitud máxima después de todos los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
bool isprime[2000010];
// Function to precalculate all the
// prime up to 10^6
void SieveOfEratosthenes(int n)
{
// Initialize prime to true
memset(isprime, true, sizeof(isprime));
isprime[1] = false;
// Iterate [2, sqrt(N)]
for (int p = 2; p * p <= n; p++) {
// If p is prime
if (isprime[p] == true) {
// Mark all multiple of p as true
for (int i = p * p; i <= n; i += p)
isprime[i] = false;
}
}
}
// Function that finds the length of
// longest subarray K distinct primes
int KDistinctPrime(int arr[], int n,
int k)
{
// Precompute all prime up to 2*10^6
SieveOfEratosthenes(2000000);
// Keep track occurrence of prime
map<int, int> cnt;
// Initialize result to -1
int result = -1;
for (int i = 0, j = -1; i < n; ++i) {
int x = arr[i];
// If number is prime then
// increment its count and
// decrease k
if (isprime[x]) {
if (++cnt[x] == 1) {
// Decrement K
--k;
}
}
// Remove required elements
// till k become non-negative
while (k < 0) {
x = arr[++j];
if (isprime[x]) {
// Decrease count so
// that it may appear
// in another subarray
// appearing after this
// present subarray
if (--cnt[x] == 0) {
// Increment K
++k;
}
}
}
// Take the max value as
// length of subarray
if (k == 0)
result = max(result, i - j);
}
// Return the final length
return result;
}
// Driver Code
int main(void)
{
// Given array arr[]
int arr[] = { 1, 2, 3, 3, 4,
5, 6, 7, 8, 9 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << KDistinctPrime(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
static boolean[] isprime = new boolean[2000010];
// Function to precalculate all the
// prime up to 10^6
static void SieveOfEratosthenes(int n)
{
// Initialize prime to true
Arrays.fill(isprime, true);
isprime[1] = false;
// Iterate [2, sqrt(N)]
for(int p = 2; p * p <= n; p++)
{
// If p is prime
if (isprime[p] == true)
{
// Mark all multiple of p as true
for(int i = p * p; i <= n; i += p)
isprime[i] = false;
}
}
}
// Function that finds the length of
// longest subarray K distinct primes
static int KDistinctPrime(int arr[], int n,
int k)
{
// Precompute all prime up to 2*10^6
SieveOfEratosthenes(2000000);
// Keep track occurrence of prime
Map<Integer, Integer> cnt = new HashMap<>();
// Initialize result to -1
int result = -1;
for(int i = 0, j = -1; i < n; ++i)
{
int x = arr[i];
// If number is prime then
// increment its count and
// decrease k
if (isprime[x])
{
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
if (cnt.get(x) == 1)
{
// Decrement K
--k;
}
}
// Remove required elements
// till k become non-negative
while (k < 0)
{
x = arr[++j];
if (isprime[x])
{
// Decrease count so
// that it may appear
// in another subarray
// appearing after this
// present subarray
cnt.put(x, cnt.getOrDefault(x, 0) - 1);
if (cnt.get(x) == 0)
{
// Increment K
++k;
}
}
}
// Take the max value as
// length of subarray
if (k == 0)
result = Math.max(result, i - j);
}
// Return the final length
return result;
}
// Driver Code
public static void main (String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 3, 3, 4,
5, 6, 7, 8, 9 };
int K = 3;
int N = arr.length;
// Function call
System.out.println(KDistinctPrime(arr, N, K));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach from collections import defaultdict isprime = [True] * 2000010 # Function to precalculate all the # prime up to 10^6 def SieveOfEratosthenes(n): isprime[1] = False # Iterate [2, sqrt(N)] p = 2 while(p * p <= n): # If p is prime if(isprime[p] == True): # Mark all multiple of p as true for i in range(p * p, n + 1, p): isprime[i] = False p += 1 # Function that finds the length of # longest subarray K distinct primes def KDistinctPrime(arr, n, k): # Precompute all prime up to 2*10^6 SieveOfEratosthenes(2000000) # Keep track occurrence of prime cnt = defaultdict(lambda : 0) # Initialize result to -1 result = -1 j = -1 for i in range(n): x = arr[i] # If number is prime then # increment its count and # decrease k if(isprime[x]): cnt[x] += 1 if(cnt[x] == 1): # Decrement K k -= 1 # Remove required elements # till k become non-negative while(k < 0): j += 1 x = arr[j] if(isprime[x]): # Decrease count so # that it may appear # in another subarray # appearing after this # present subarray cnt[x] -= 1 if(cnt[x] == 0): # Increment K k += 1 # Take the max value as # length of subarray if(k == 0): result = max(result, i - j) # Return the final length return result # Driver Code # Given array arr[] arr = [ 1, 2, 3, 3, 4, 5, 6, 7, 8, 9 ] K = 3 N = len(arr) # Function call print(KDistinctPrime(arr, N, K)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static bool[] isprime = new bool[2000010];
// Function to precalculate all the
// prime up to 10^6
static void SieveOfEratosthenes(int n)
{
// Initialize prime to true
for(int i = 0; i < isprime.Length; i++)
isprime[i] = true;
isprime[1] = false;
// Iterate [2, sqrt(N)]
for(int p = 2; p * p <= n; p++)
{
// If p is prime
if (isprime[p] == true)
{
// Mark all multiple of p as true
for(int i = p * p; i <= n; i += p)
isprime[i] = false;
}
}
}
// Function that finds the length of
// longest subarray K distinct primes
static int KDistinctPrime(int []arr,
int n, int k)
{
// Precompute all prime up to 2*10^6
SieveOfEratosthenes(2000000);
// Keep track occurrence of prime
Dictionary<int,
int> cnt = new Dictionary<int,
int>();
// Initialize result to -1
int result = -1;
for(int i = 0, j = -1; i < n; ++i)
{
int x = arr[i];
// If number is prime then
// increment its count and
// decrease k
if (isprime[x])
{
if(cnt.ContainsKey(x))
cnt[x] = cnt[x] + 1;
else
cnt.Add(x, 1);
if (cnt[x] == 1)
{
// Decrement K
--k;
}
}
// Remove required elements
// till k become non-negative
while (k < 0)
{
x = arr[++j];
if (isprime[x])
{
// Decrease count so
// that it may appear
// in another subarray
// appearing after this
// present subarray
if(cnt.ContainsKey(x))
cnt[x] = cnt[x] - 1;
else
cnt.Add(x, 0);
if (cnt[x] == 0)
{
// Increment K
++k;
}
}
}
// Take the max value as
// length of subarray
if (k == 0)
result = Math.Max(result, i - j);
}
// Return the readonly length
return result;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = {1, 2, 3, 3, 4,
5, 6, 7, 8, 9};
int K = 3;
int N = arr.Length;
// Function call
Console.WriteLine(KDistinctPrime(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
let isprime = new Array(2000010);
// Function to precalculate all the
// prime up to 10^6
function SieveOfEratosthenes(n)
{
// Initialize prime to true
isprime.fill(true);
isprime[1] = false;
// Iterate [2, sqrt(N)]
for(let p = 2; p * p <= n; p++)
{
// If p is prime
if (isprime[p] == true)
{
// Mark all multiple of p as true
for(let i = p * p; i <= n; i += p)
isprime[i] = false;
}
}
}
// Function that finds the length of
// longest subarray K distinct primes
function KDistinctPrime(arr, n, k)
{
// Precompute all prime up to 2*10^6
SieveOfEratosthenes(2000000);
// Keep track occurrence of prime
let cnt = new Map();
// Initialize result to -1
let result = -1;
for(let i = 0, j = -1; i < n; ++i)
{
let x = arr[i];
// If number is prime then
// increment its count and
// decrease k
if (isprime[x])
{
if(cnt.has(x))
cnt.set(x, cnt.get(x)+1)
else
cnt.set(x, 1);
if (cnt.get(x) == 1)
{
// Decrement K
--k;
}
}
// Remove required elements
// till k become non-negative
while (k < 0)
{
x = arr[++j];
if (isprime[x])
{
// Decrease count so
// that it may appear
// in another subarray
// appearing after this
// present subarray
if(cnt.has(x))
cnt.set(x, cnt.get(x) - 1)
else
cnt.set(x, -1);
if (cnt.get(x) == 0)
{
// Increment K
++k;
}
}
}
// Take the max value as
// length of subarray
if (k == 0)
result = Math.max(result, i - j);
}
// Return the final length
return result;
}
// Given array arr[]
let arr = [ 1, 2, 3, 3, 4, 5, 6, 7, 8, 9 ];
let K = 3;
let N = arr.length;
// Function call
document.write(KDistinctPrime(arr, N, K));
</script>
Producción:
8
Complejidad de tiempo: O(N*log(log(N))), donde N es el elemento máximo en la array dada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA