Subarreglo de tamaño K con suma prima

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.

  1. 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.
  2. Inicialice una variable, diga currSum para almacenar la suma de elementos de subarreglos de tamaño K .
  3. Encuentre la suma de los primeros K elementos de la array y guárdela en currSum .
  4. 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.
  5. 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)

Publicación traducida automáticamente

Artículo escrito por Rajput-Ji y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *