Given an array, arr[] of size N and an integer K, the task is to print a subarray of size K whose sum of elements is a prime number. If more than one such subarray exists, then print any one of them.
Examples:
Input: arr[] = {20, 7, 5, 4, 3, 11, 99, 87, 23, 45}, K = 4
Output: 7 5 4 3
Explanation: Sum of the elements of the subarray {7, 5, 4, 3} is 19.
Therefore, the required output is 7 5 4 3.Input: arr[] = {11, 13, 17}, K = 1
Output: 11
Approach: To solve the problem, the idea is to find the sum of all subarrays of size K using the Sliding Window technique and check if it is prime or not. Follow the steps below to solve the problem.
- Generate all the prime numbers in the range [1, 1000000] using the sieve of Eratosthenes to check if a number is prime or not.
- Initialize a variable, say currSum to store the sum of elements of subarrays of size K.
- Find the sum of the first K elements of the array and store it in currSum.
- Iterate over the remaining array elements one by one, and update currSum by adding the ith element and removing the (i – K)th element from the array. Now, check if currSum is prime or not.
- If currSum is found to be prime, then print all the elements of the current subarray.
Below is the implementation of the above approach:
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 primevoid 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 Codeint 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 approachimport 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 primestatic 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 Codepublic 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 primedef 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 Codeif __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 approachusing 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 primestatic 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 Codepublic 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 primefunction 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 Codevar 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> |
Output:
7 5 4 3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
