1.
Introduction
1.1.
Pre-requisites
2.
Problem Statement
2.1.
Example
3.
Approach
4.
C++ Implementation
4.1.
Time Complexity
4.2.
Space Complexity
5.
6.
Key Takeaways
Last Updated: Mar 27, 2024

Find the longest subarray with Prime sum in given Array

Yukti Kumari
0 upvote

Introduction

In this article, we will discuss yet another problem based on subarrays in a very interactive and intuitive way. We will start by brushing up on some important concepts that will help you understand the problem more effectively and easily. So, without much ado, let’s get started by seeing the prerequisites.

Pre-requisites

Some of the prerequisites required to solve this problem are as follows:

• Subarray - A contiguous subsequence of an array is called a subarray.
Example - Given an array A = [1,2,3,5,6], some of the subarrays are [1],[2],[3],[6],[1,2,3], [3,5,6] etc.

• Prime number- A number is said to be prime if it has only two factors, 1 and the number itself.
Example- 2,3,5,7,11 etc., are all prime numbers because they are not divisible by any other number than 1 and itself.

• Sieve of Eratosthenes- When we talk about the prime numbers in coding, it comes with the need for a method by which we can check if a number is prime or not. Among many techniques, one such method is the Sieve of Eratostheneswhich helps us find all the prime numbers up to any given limit.
Example - If you want to find all primes in the range [1,n], we can use Sieve of Eratosthenes, which uses O(nloglogn) operations.

If you are not familiar with the concept of subarrays with a given sum, then you must read this article - What Is Subarray With Given Sum? to make the most out of this blog.

Let’s get started with the problem statement.

Problem Statement

You are given an array A[] of size N, consisting of positive integers, i.e. A[i]>=0, ∀ 0<=i<N. Find the length of the longest subarray having a prime sum.

What do you understand by “subarray having prime sum”?

A subarray A[i,j] is said to have prime sum if the sum of all the elements of this subarray is a prime number i.e. if S = A[i] + A[i+1] + … + A[j], then S is a prime number.

Why not look at a few examples with inputs and desired outputs for this problem statement!!

Example

Input:

array A[] = {1,2,3,7,11} N=5

Output:

4

Some of the subarrays of A[] = {1,2,3,7,11} having prime sum are:

• {3} → Sum=3
• {7} → Sum=7
• {11} → Sum=11
• {2} → Sum=2
• {2,3} → Sum=5
• {1,2} → Sum=3
• {1,2,3,7} → Sum=13
• {2,3,7,11} → Sum=23

Among all such subarrays, the maximum length is 4, and we have two subarrays having the maximum length and prime sum. Hence, the output is 4.

Please try to solve this problem on your own before moving on to further discussion here

In the next section, let’s move on to the approach and ideas about solving the problem.

Also see, Euclid GCD Algorithm

Approach

In the given problem, we are interested in all the subarrays which have a prime sum, and among all such subarrays, we have to find the one having the maximum length.

The problem is quite straightforward and easy to implement. We will now see the entire approach step by step:

• Define a variable “res” and initialize it with 0. It stores the length of the longest subarray with a prime sum.

• Iterate over all the subarrays using nested loops and, in each iteration, find the sum of the current subarray. Let it be currSum.

• Check if currSum is prime or not. Here, we will use Sieve of Eratosthenes to find if the currSum is prime or not as we know the upper limit of the sum a subarray can have. How? See, the longest subarray of an array will be the array itself. Thus the maximum value of currSum will be the sum of all array elements.

• First, check if the sum of the given array is prime. If prime, then return “n” as the array itself is the required longest subarray having prime sum.

• If the currSum is prime and the length of the current subarray is greater than the longest subarray found so far, then update the res as res=current subarray length.

• Finally, return the result.

Let’s see the code implementation and the time and space complexity analysis in the next section.

C++ Implementation

/*
C++ Program to find the longest subarray with Prime sum in given Array
*/
#include <bits/stdc++.h>
using namespace std;

void SieveOfEratosthenes(vector<bool> &isPrime, int n)
{
// 0 and 1 are not prime
isPrime[0] = false;
if (n == 1)
return;
isPrime[1] = false;
for (int i = 2; i <= n; i++)
{
if (isPrime[i])
{
for (int j = i * i; j <= n; j += i)
{
isPrime[j] = false;
}
}
}
}

// function to find length of the longest subarray with Prime sum
int longestSubarrayWithPrimeSum(vector<int> &arr, int num)
{
int res = 0, arraySum = 0;

// finding sum of given array
for (int i = 0; i < num; i++)
{
arraySum += arr[i];
}

// finding all prime between [1, arraySum] using sieve
vector<bool> isPrime(arraySum + 1, true);
SieveOfEratosthenes(isPrime, arraySum);
if (isPrime[arraySum])
{
return num;
}
for (int start = 0; start < num; start++)
{
int currSum = 0;
for (int end = start; end < num; end++)
{
currSum += arr[end];
// subarray - arr[start,end]
if (isPrime[currSum])
{
int currLen = end - start + 1;
if (currLen > res)
{
res = currLen;
}
}
}
}
return res;
}

int main()
{
vector<int> arr = {1, 2, 3, 7, 11};
int num = arr.size();

int res = longestSubarrayWithPrimeSum(arr, num);
cout << "The length of the longest subarray with Prime sum in given Array is: " << res << endl;
}

Output

The length of the longest subarray with Prime sum in given Array is: 4

Time Complexity

O(max((n2), (mloglogm))), where n=size of the given array and m= arraySum.

Here, we use two nested for loops each of length n whose time complexity O(n2). And to find all prime numbers in the range [1, arraySum] we use sieveOfEratosthenes which takes O(mloglogm) where m=arraySum.

Hence, the total time complexity is O(n2) + O(mloglogm) which is equal to O(max((n2), (mloglogm))).

Space Complexity

O(arraySum). where  arraySum=sum of all the elements of the array. Since we use an array of size = arraySum to find all primes in the range [1,arraySum].

Check out this problem - Subarray With 0 Sum

1. How many Subarrays can be formed in an array of size N?
The number of all possible subarrays of an array of size N is N * (N + 1)/2.

2. Are all subarrays also subsequences of an array?
Every subarray is also a subsequence because you can obtain a subarray by removing all the elements before and after this subarray, but the reverse is not true. So, every subsequence is not a subarray because a subsequence does not necessarily consist of contiguous elements.

3. How many subsequences are there in an array?
The total number of subsequences of array is 2n which is obtained by -  nC0 + nC1 + nC2 + … nCn = 2n.

Key Takeaways

In this article, we discussed a problem based on subarrays to find the longest subarray with a prime sum. We brushed upon the concepts like subarrays and sieve of Eratosthenes which helped us to solve the problem easily.

Check out the blog section - Prime numbers, where you will find some interesting articles dealing with concepts related to prime numbers.

Problems you should practice in a row to make your understanding rock solid -

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Live masterclass