Dados tres enteros X , Y y P , la tarea es encontrar el tamaño mínimo de ventana K tal que cada ventana en el rango [X, Y] de este tamaño tenga al menos P números primos.
Ejemplos:
Entrada: X = 2, Y = 8, P = 2
Salida: 4
Explicación:
En el rango [2, 8], el tamaño de ventana de 4 contiene al menos 2 números primos en cada ventana.
Ventanas posibles:
{2, 3, 4, 5}: número de primos = 3
{3, 4, 5, 6}: número de números primos = 2
{4, 5, 6, 7}: número de números primos = 2
{5 , 6, 7, 8} – Número de primos = 2
Entrada: X = 12, Y = 42, P = 3
Salida: 14
Explicación:
En el rango [12, 42], el tamaño de ventana de 14 contiene al menos 3 primos en cada ventana.
Enfoque ingenuo: recorra todos los tamaños de ventana posibles, para cada tamaño de ventana, recorra el rango [X, Y] y verifique que cada ventana contenga al menos K números primos. El mínimo de estos tamaños de ventana será el valor deseado.
Enfoque eficiente: la observación clave en este problema es que si un tamaño de ventana W es el tamaño de ventana mínimo que satisface la condición, entonces todos los tamaños de ventana en el rango [W, Y – X + 1] cumplirán la condición. Usando esto, podemos reducir nuestro espacio de búsqueda en cada paso a la mitad, que es precisamente la idea de Binary Search . A continuación se muestra la ilustración de los pasos:
- Espacio de búsqueda: el espacio de búsqueda para este problema puede ser la longitud mínima del tamaño de la ventana que es 1 y el tamaño máximo de la ventana puede ser la diferencia entre el valor final del rango y el valor inicial del rango.
low = 1 high = Y - X + 1
- Siguiente espacio de búsqueda: en cada paso, generalmente, la idea es verificar que para el tamaño de ventana dado, los primos en cada ventana pueden tener P primos o no con la ayuda de la técnica de ventana deslizante . Considerando que el espacio de búsqueda para el problema se puede reducir sobre la base de la siguiente decisión:
- Caso 1: cuando el número de primos en cada ventana contiene al menos P primos, entonces el tamaño de la ventana se puede reducir para encontrar el tamaño de la ventana menor que la ventana actual.
- Caso 1: cuando el número de primos en cada ventana contiene al menos P primos, entonces el tamaño de la ventana se puede reducir para encontrar el tamaño de la ventana menor que la ventana actual.
if (checkPPrimes(mid) == True)
high = mid - 1
- Caso 2: cuando el número de primos en cada ventana no tiene, entonces el tamaño de la ventana debe ser mayor que el tamaño de la ventana actual. Después,
if (checkPPrimes(mid) == False)
low = mid + 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum window size in the range
// such that each window of that size
// contains atleast P primes
#include <bits/stdc++.h>
using namespace std;
// Function to check that a number is
// a prime or not in O(sqrt(N))
bool isPrime(int N)
{
if (N < 2)
return false;
if (N < 4)
return true;
if ((N & 1) == 0)
return false;
if (N % 3 == 0)
return false;
int curr = 5, s = sqrt(N);
// Loop to check if any number
// number is divisible by any
// other number or not
while (curr <= s) {
if (N % curr == 0)
return false;
curr += 2;
if (N % curr == 0)
return false;
curr += 4;
}
return true;
}
// Function to check whether window
// size satisfies condition or not
bool check(int s, int p,
int prefix_sum[], int n)
{
bool satisfies = true;
// Loop to check each window of
// size have atleast P primes
for (int i = 0; i < n; i++) {
if (i + s - 1 >= n)
break;
// Checking condition
// using prefix sum
if (prefix_sum[i + s - 1] -
(i - 1 >= 0 ?
prefix_sum[i - 1] : 0) < p)
satisfies = false;
}
return satisfies;
}
// Function to find the minimum
// window size possible for the
// given range in X and Y
int minimumWindowSize(int x, int y,
int p)
{
// Prefix array
int prefix_sum[y - x + 1] = { 0 };
// Mark those numbers
// which are primes as 1
for (int i = x; i <= y; i++) {
if (isPrime(i))
prefix_sum[i - x] = 1;
}
// Convert to prefix sum
for (int i = 1; i < y - x + 1; i++)
prefix_sum[i] +=
prefix_sum[i - 1];
// Applying binary search
// over window size
int low = 1, high = y - x + 1;
int mid;
while (high - low > 1) {
mid = (low + high) / 2;
// Check whether mid satisfies
// the condition or not
if (check(mid, p,
prefix_sum, y - x + 1)) {
// If satisfies search
// in first half
high = mid;
}
// Else search in second half
else
low = mid;
}
if (check(low, p,
prefix_sum, y - x + 1))
return low;
return high;
}
// Driver Code
int main()
{
int x = 12;
int y = 42;
int p = 3;
cout << minimumWindowSize(x, y, p);
return 0;
}
Java
// Java implementation to find the
// minimum window size in the range
// such that each window of that size
// contains atleast P primes
import java.util.*;
class GFG{
// Function to check that a number is
// a prime or not in O(Math.sqrt(N))
static boolean isPrime(int N)
{
if (N < 2)
return false;
if (N < 4)
return true;
if ((N & 1) == 0)
return false;
if (N % 3 == 0)
return false;
int curr = 5, s = (int) Math.sqrt(N);
// Loop to check if any number
// number is divisible by any
// other number or not
while (curr <= s) {
if (N % curr == 0)
return false;
curr += 2;
if (N % curr == 0)
return false;
curr += 4;
}
return true;
}
// Function to check whether window
// size satisfies condition or not
static boolean check(int s, int p,
int prefix_sum[], int n)
{
boolean satisfies = true;
// Loop to check each window of
// size have atleast P primes
for (int i = 0; i < n; i++) {
if (i + s - 1 >= n)
break;
// Checking condition
// using prefix sum
if (prefix_sum[i + s - 1] -
(i - 1 >= 0 ?
prefix_sum[i - 1] : 0) < p)
satisfies = false;
}
return satisfies;
}
// Function to find the minimum
// window size possible for the
// given range in X and Y
static int minimumWindowSize(int x, int y,
int p)
{
// Prefix array
int []prefix_sum = new int[y - x + 1];
// Mark those numbers
// which are primes as 1
for (int i = x; i <= y; i++) {
if (isPrime(i))
prefix_sum[i - x] = 1;
}
// Convert to prefix sum
for (int i = 1; i < y - x + 1; i++)
prefix_sum[i] +=
prefix_sum[i - 1];
// Applying binary search
// over window size
int low = 1, high = y - x + 1;
int mid;
while (high - low > 1) {
mid = (low + high) / 2;
// Check whether mid satisfies
// the condition or not
if (check(mid, p,
prefix_sum, y - x + 1)) {
// If satisfies search
// in first half
high = mid;
}
// Else search in second half
else
low = mid;
}
if (check(low, p,
prefix_sum, y - x + 1))
return low;
return high;
}
// Driver Code
public static void main(String[] args)
{
int x = 12;
int y = 42;
int p = 3;
System.out.print(minimumWindowSize(x, y, p));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 implementation to find the # minimum window size in the range # such that each window of that size # contains atleast P primes from math import sqrt # Function to check that a number is # a prime or not in O(sqrt(N)) def isPrime(N): if (N < 2): return False if (N < 4): return True if ((N & 1) == 0): return False if (N % 3 == 0): return False curr = 5 s = sqrt(N) # Loop to check if any number # number is divisible by any # other number or not while (curr <= s): if (N % curr == 0): return False curr += 2 if (N % curr == 0): return False curr += 4 return True # Function to check whether window # size satisfies condition or not def check(s, p, prefix_sum, n): satisfies = True # Loop to check each window of # size have atleast P primes for i in range(n): if (i + s - 1 >= n): break # Checking condition # using prefix sum if (i - 1 >= 0): x = prefix_sum[i - 1] else: x = 0 if (prefix_sum[i + s - 1] - x < p): satisfies = False return satisfies # Function to find the minimum # window size possible for the # given range in X and Y def minimumWindowSize(x, y, p): # Prefix array prefix_sum = [0]*(y - x + 1) # Mark those numbers # which are primes as 1 for i in range(x ,y+1): if (isPrime(i)): prefix_sum[i - x] = 1 # Convert to prefix sum for i in range(1 ,y - x + 1): prefix_sum[i] += prefix_sum[i - 1] # Applying binary search # over window size low = 1 high = y - x + 1 while (high - low > 1): mid = (low + high) // 2 # Check whether mid satisfies # the condition or not if (check(mid, p ,prefix_sum, y - x + 1)): # If satisfies search # in first half high = mid # Else search in second half else: low = mid if (check(low, p, prefix_sum, y - x + 1)): return low return high # Driver Code x = 12 y = 42 p = 3 print(minimumWindowSize(x, y, p)) # This code is contributed by shubhamsingh10
C#
// C# implementation to find the
// minimum window size in the range
// such that each window of that size
// contains atleast P primes
using System;
class GFG{
// Function to check that a number is
// a prime or not in O(Math.Sqrt(N))
static bool isPrime(int N)
{
if (N < 2)
return false;
if (N < 4)
return true;
if ((N & 1) == 0)
return false;
if (N % 3 == 0)
return false;
int curr = 5, s = (int) Math.Sqrt(N);
// Loop to check if any number
// number is divisible by any
// other number or not
while (curr <= s) {
if (N % curr == 0)
return false;
curr += 2;
if (N % curr == 0)
return false;
curr += 4;
}
return true;
}
// Function to check whether window
// size satisfies condition or not
static bool check(int s, int p,
int []prefix_sum, int n)
{
bool satisfies = true;
// Loop to check each window of
// size have atleast P primes
for (int i = 0; i < n; i++) {
if (i + s - 1 >= n)
break;
// Checking condition
// using prefix sum
if (prefix_sum[i + s - 1] -
(i - 1 >= 0 ?
prefix_sum[i - 1] : 0) < p)
satisfies = false;
}
return satisfies;
}
// Function to find the minimum
// window size possible for the
// given range in X and Y
static int minimumWindowSize(int x, int y,
int p)
{
// Prefix array
int []prefix_sum = new int[y - x + 1];
// Mark those numbers
// which are primes as 1
for (int i = x; i <= y; i++) {
if (isPrime(i))
prefix_sum[i - x] = 1;
}
// Convert to prefix sum
for (int i = 1; i < y - x + 1; i++)
prefix_sum[i] +=
prefix_sum[i - 1];
// Applying binary search
// over window size
int low = 1, high = y - x + 1;
int mid;
while (high - low > 1) {
mid = (low + high) / 2;
// Check whether mid satisfies
// the condition or not
if (check(mid, p,
prefix_sum, y - x + 1)) {
// If satisfies search
// in first half
high = mid;
}
// Else search in second half
else
low = mid;
}
if (check(low, p,
prefix_sum, y - x + 1))
return low;
return high;
}
// Driver Code
public static void Main(String[] args)
{
int x = 12;
int y = 42;
int p = 3;
Console.Write(minimumWindowSize(x, y, p));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript implementation to find the
// minimum window size in the range
// such that each window of that size
// contains atleast P primes
// Function to check that a number is
// a prime or not in O(Math.sqrt(N))
function isPrime(N)
{
if (N < 2)
return false;
if (N < 4)
return true;
if ((N & 1) == 0)
return false;
if (N % 3 == 0)
return false;
let curr = 5, s = Math.floor(Math.sqrt(N));
// Loop to check if any number
// number is divisible by any
// other number or not
while (curr <= s) {
if (N % curr == 0)
return false;
curr += 2;
if (N % curr == 0)
return false;
curr += 4;
}
return true;
}
// Function to check whether window
// size satisfies condition or not
function check(s, p,
prefix_sum, n)
{
let satisfies = true;
// Loop to check each window of
// size have atleast P primes
for (let i = 0; i < n; i++) {
if (i + s - 1 >= n)
break;
// Checking condition
// using prefix sum
if (prefix_sum[i + s - 1] -
(i - 1 >= 0 ?
prefix_sum[i - 1] : 0) < p)
satisfies = false;
}
return satisfies;
}
// Function to find the minimum
// window size possible for the
// given range in X and Y
function minimumWindowSize(x, y, p)
{
// Prefix array
let prefix_sum = new Array(y - x + 1).fill(0);
// Mark those numbers
// which are primes as 1
for (let i = x; i <= y; i++) {
if (isPrime(i))
prefix_sum[i - x] = 1;
}
// Convert to prefix sum
for (let i = 1; i < y - x + 1; i++)
prefix_sum[i] +=
prefix_sum[i - 1];
// Applying binary search
// over window size
let low = 1, high = y - x + 1;
let mid;
while (high - low > 1) {
mid = Math.floor((low + high) / 2);
// Check whether mid satisfies
// the condition or not
if (check(mid, p,
prefix_sum, y - x + 1)) {
// If satisfies search
// in first half
high = mid;
}
// Else search in second half
else
low = mid;
}
if (check(low, p,
prefix_sum, y - x + 1))
return low;
return high;
}
// Driver Code
let x = 12;
let y = 42;
let p = 3;
document.write(minimumWindowSize(x, y, p));
</script>
Producción:
14
Complejidad temporal: O(N*log(N))
Espacio auxiliar: O(N)