Dado un arreglo , arr[] de tamaño N y un entero K , la tarea es imprimir un subarreglo de tamaño K cuya suma de elementos sea un número primo . Si existe más de un subarreglo, imprima cualquiera de ellos.
Ejemplos:
Entrada: arr[] = {20, 7, 5, 4, 3, 11, 99, 87, 23, 45}, K = 4
Salida: 7 5 4 3
Explicación: Suma de los elementos del subarreglo {7, 5 , 4, 3} es 19.
Por lo tanto, la salida requerida es 7 5 4 3.Entrada: arr[] = {11, 13, 17}, K = 1
Salida: 11
Planteamiento: Para resolver el problema, la idea es encontrar la suma de todos los subarreglos de tamaño K utilizando la técnica de la ventana deslizante y verificar si es primo o no . Siga los pasos a continuación para resolver el problema.
- Genera todos los números primos en el rango [1, 1000000] usando el tamiz de Eratóstenes para comprobar si un número es primo o no.
- Inicialice una variable, diga currSum para almacenar la suma de elementos de subarreglos de tamaño K .
- Encuentre la suma de los primeros K elementos de la array y guárdela en currSum .
- Repita los elementos restantes de la array uno por uno y actualice currSum agregando el i -ésimo elemento y eliminando el (i – K) -ésimo elemento de la array. Ahora, verifique si currSum es primo o no.
- Si se encuentra que currSum es primo, imprima todos los elementos del subarreglo actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Generate all prime numbers
// in the range [1, 1000000]
void sieve(bool prime[])
{
// Set all numbers as
// prime initially
for (int i = 0; i < 1000000;
i++) {
prime[i] = true;
}
// Mark 0 and 1 as non-prime
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 1000000; i++) {
// If current element is prime
if (prime[i]) {
// Mark all its multiples
// as non-prime
for (int j = i * i; j <= 1000000;
j += i) {
prime[j] = false;
}
}
}
}
// Function to print the subarray
// whose sum of elements is prime
void subPrimeSum(int N, int K,
int arr[],
bool prime[])
{
// Store the current subarray
// of size K
int currSum = 0;
// Calculate the sum of
// first K elements
for (int i = 0; i < K; i++) {
currSum += arr[i];
}
// Check if currSum is prime
if (prime[currSum]) {
for (int i = 0; i < K; i++) {
cout << arr[i] << " ";
}
return;
}
// Store the start and last
// index of subarray of size K
int st = 1, en = K;
// Iterate over remaining array
while (en < N) {
currSum += arr[en] - arr[st - 1];
// Check if currSum
if (prime[currSum]) {
for (int i = st; i <= en; i++) {
cout << arr[i] << " ";
}
return;
}
en++;
st++;
}
}
// Driver Code
int main()
{
int arr[] = { 20, 7, 5, 4, 3, 11,
99, 87, 23, 45 };
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
bool prime[1000000];
sieve(prime);
subPrimeSum(N, K, arr, prime);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Generate all prime numbers
// in the range [1, 1000000]
static void sieve(boolean prime[])
{
// Set all numbers as
// prime initially
for (int i = 0; i < 1000000; i++)
{
prime[i] = true;
}
// Mark 0 and 1 as non-prime
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 1000000; i++)
{
// If current element is prime
if (prime[i])
{
// Mark all its multiples
// as non-prime
for (int j = i * i; j < 1000000; j += i)
{
prime[j] = false;
}
}
}
}
// Function to print the subarray
// whose sum of elements is prime
static void subPrimeSum(int N, int K,
int arr[],
boolean prime[])
{
// Store the current subarray
// of size K
int currSum = 0;
// Calculate the sum of
// first K elements
for (int i = 0; i < K; i++)
{
currSum += arr[i];
}
// Check if currSum is prime
if (prime[currSum])
{
for (int i = 0; i < K; i++)
{
System.out.print(arr[i] + " ");
}
return;
}
// Store the start and last
// index of subarray of size K
int st = 1, en = K;
// Iterate over remaining array
while (en < N)
{
currSum += arr[en] - arr[st - 1];
// Check if currSum
if (prime[currSum])
{
for (int i = st; i <= en; i++)
{
System.out.print(arr[i] + " ");
}
return;
}
en++;
st++;
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {20, 7, 5, 4, 3, 11,
99, 87, 23, 45};
int K = 4;
int N = arr.length;
boolean []prime = new boolean[1000000];
sieve(prime);
subPrimeSum(N, K, arr, prime);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach # Generate all prime numbers # in the range [1, 1000000] def sieve(prime): # Set all numbers as # prime initially for i in range(1000000): prime[i] = True # Mark 0 and 1 as non-prime prime[0] = prime[1] = False for i in range(2, 1000 + 1): # If current element is prime if (prime[i]): # Mark all its multiples # as non-prime for j in range(i * i, 1000000, i): prime[j] = False return prime # Function to print the subarray # whose sum of elements is prime def subPrimeSum(N, K, arr, prime): # Store the current subarray # of size K currSum = 0 # Calculate the sum of # first K elements for i in range(0, K): currSum += arr[i] # Check if currSum is prime if (prime[currSum]): for i in range(K): print(arr[i], end = " ") return # Store the start and last # index of subarray of size K st = 1 en = K # Iterate over remaining array while (en < N): currSum += arr[en] - arr[st - 1] # Check if currSum if (prime[currSum]): for i in range(st, en + 1): print(arr[i], end = " ") return en += 1 st += 1 # Driver Code if __name__ == '__main__': arr = [ 20, 7, 5, 4, 3, 11, 99, 87, 23, 45 ] K = 4 N = len(arr) prime = [False] * 1000000 prime = sieve(prime) subPrimeSum(N, K, arr, prime) # This code is contributed by Amit Katiyar
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Generate all prime numbers
// in the range [1, 1000000]
static void sieve(bool []prime)
{
// Set all numbers as
// prime initially
for (int i = 0; i < 1000000; i++)
{
prime[i] = true;
}
// Mark 0 and 1 as non-prime
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 1000000; i++)
{
// If current element is prime
if (prime[i])
{
// Mark all its multiples
// as non-prime
for (int j = i * i; j < 1000000; j += i)
{
prime[j] = false;
}
}
}
}
// Function to print the subarray
// whose sum of elements is prime
static void subPrimeSum(int N, int K,
int []arr,
bool []prime)
{
// Store the current subarray
// of size K
int currSum = 0;
// Calculate the sum of
// first K elements
for (int i = 0; i < K; i++)
{
currSum += arr[i];
}
// Check if currSum is prime
if (prime[currSum])
{
for (int i = 0; i < K; i++)
{
Console.Write(arr[i] + " ");
}
return;
}
// Store the start and last
// index of subarray of size K
int st = 1, en = K;
// Iterate over remaining array
while (en < N)
{
currSum += arr[en] - arr[st - 1];
// Check if currSum
if (prime[currSum])
{
for (int i = st; i <= en; i++)
{
Console.Write(arr[i] + " ");
}
return;
}
en++;
st++;
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {20, 7, 5, 4, 3, 11,
99, 87, 23, 45};
int K = 4;
int N = arr.Length;
bool []prime = new bool[1000000];
sieve(prime);
subPrimeSum(N, K, arr, prime);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to implement
// the above approach
// Generate all prime numbers
// in the range [1, 1000000]
function sieve(prime)
{
// Set all numbers as
// prime initially
for (var i = 0; i < 1000000;
i++) {
prime[i] = true;
}
// Mark 0 and 1 as non-prime
prime[0] = prime[1] = false;
for (var i = 2; i * i <= 1000000; i++)
{
// If current element is prime
if (prime[i])
{
// Mark all its multiples
// as non-prime
for (var j = i * i; j <= 1000000;
j += i) {
prime[j] = false;
}
}
}
}
// Function to print the subarray
// whose sum of elements is prime
function subPrimeSum( N, K, arr, prime)
{
// Store the current subarray
// of size K
var currSum = 0;
// Calculate the sum of
// first K elements
for (var i = 0; i < K; i++) {
currSum += arr[i];
}
// Check if currSum is prime
if (prime[currSum]) {
for (var i = 0; i < K; i++) {
document.write(arr[i] + " ");
}
return;
}
// Store the start and last
// index of subarray of size K
var st = 1, en = K;
// Iterate over remaining array
while (en < N) {
currSum += arr[en] - arr[st - 1];
// Check if currSum
if (prime[currSum]) {
for (var i = st; i <= en; i++) {
document.write(arr[i] + " ");
}
return;
}
en++;
st++;
}
}
// Driver Code
var arr = [ 20, 7, 5, 4, 3, 11,
99, 87, 23, 45 ]
var K = 4;
var N = arr.length;
prime = Array(1000000).fill(0);
sieve(prime);
subPrimeSum(N, K, arr, prime);
// This code is contributed by rrrtnx.
</script>
Producción:
7 5 4 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)