Find the longest subarray with Prime sum in given Array

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((n²), (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(n²). 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(n²) + O(mloglogm) which is equal to O(max((n²), (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

Frequently Asked Questions

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 2ⁿ which is obtained by -  nC0 + nC1 + nC2 + … nCn = 2ⁿ.

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 - 

• Subarray with given Sum
• Longest Subarray Zero Sum

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!