Given an array arr[] of integers of size n, find the maximum sum of a continuous subarray such that the subarray only contains prime integers. In other words, no non-prime integer should appear within the chosen subarray.
Examples:
Input: arr[] = [1, 7, 4, 2, 3, 8, 5, 11, 13], n = 9
Output: 29
Explanation: The subarray [5, 11, 13] is the only subarray with prime integers and with a maximum sum of 29.Input: arr = [1, 4, 6, 7, 10], n = 5
Output: 7
Explanation: The maximum sum of a continuous subarray such that the subarray only contains prime integers is {7} with sum 7.
Naive Approach: The basic way to solve the problem is as follows:
The idea involves checking all possible subarrays that only contain prime integers and keeping track of the maximum sum.
Steps that were to follow the above approach:
- Initialize maxSum to 0
- Loop through all subarrays of arr
- Check if the current subarray only contains prime integers
- If it does, calculate its sum
- If its sum is greater than maxSum, update maxSum
- Check if the current subarray only contains prime integers
- Return maxSum
Below is the code to implement the above steps:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// function to check if a number is primebool isPrime(int n){ if (n <= 1) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true;}// Function to find the maximum sum// of a continuous subarray that// contains only prime integersint maxPrimeSubarraySum(int arr[], int n){ int maxSum = 0; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { if (isPrime(arr[j])) { // If integer is prime, // add it to the current // sum and update max sum // if necessary currentSum += arr[j]; maxSum = max(maxSum, currentSum); } else { // If integer is not prime, // break and move to // next subarray break; } } } return maxSum;}// Driver's codeint main(){ int arr[] = { 1, 3, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); // Call maxPrimeSubarraySum function to // find the maximum sum of a continuous // subarray with prime integers int sum = maxPrimeSubarraySum(arr, n); cout << "Maximum sum of prime subarray is: " << sum << endl; return 0;} |
Java
import java.util.*;public class Main { // function to check if a number is prime public static boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } return true; } // function to find the maximum sum of a continuous // subarray that contains only prime integers public static int maxPrimeSubarraySum(int[] arr, int n) { int maxSum = 0; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { if (isPrime( arr[j])) { // if integer is prime, // add it to the current // sum and update max sum // if necessary currentSum += arr[j]; maxSum = Math.max(maxSum, currentSum); } else { // if integer is not prime, break and // move to next subarray break; } } } return maxSum; } // Driver's code public static void main(String[] args) { int[] arr = { 1, 3, 5, 6, 7 }; int n = arr.length; // call maxPrimeSubarraySum function to find the // maximum sum of a continuous subarray with prime // integers int sum = maxPrimeSubarraySum(arr, n); System.out.println( "Maximum sum of prime subarray is: " + sum); }} |
Python3
import math# function to check if a number is primedef isPrime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n))+1): if n % i == 0: return False return True# function to find the maximum sum of a continuous subarray that contains only prime integersdef maxPrimeSubarraySum(arr): n = len(arr) maxSum = 0 for i in range(n): currentSum = 0 for j in range(i, n): if isPrime(arr[j]): # if integer is prime, add it to the current sum and update max sum if necessary currentSum += arr[j] maxSum = max(maxSum, currentSum) else: # if integer is not prime, break and move to next subarray break return maxSumarr = [1, 3, 5, 6, 7]# call maxPrimeSubarraySum function to find the maximum sum of a continuous subarray with prime integerssum = maxPrimeSubarraySum(arr)print("Maximum sum of prime subarray is:", sum) |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to check if a number is prime static bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } // Function to find the maximum sum // of a continuous subarray that // contains only prime integers static int MaxPrimeSubarraySum(int[] arr, int n) { int maxSum = 0; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { if (IsPrime(arr[j])) { // If integer is prime, // add it to the current // sum and update max sum // if necessary currentSum += arr[j]; maxSum = Math.Max(maxSum, currentSum); } else { // If integer is not prime, // break and move to // next subarray break; } } } return maxSum; } static void Main(string[] args) { int[] arr = { 1, 3, 5, 6, 7 }; int n = arr.Length; // Call MaxPrimeSubarraySum function to // find the maximum sum of a continuous // subarray with prime integers int sum = MaxPrimeSubarraySum(arr, n); Console.WriteLine("Maximum sum of prime subarray is: " + sum); }} |
Javascript
// function to check if a number is primefunction isPrime(n) { if (n <= 1) return false; for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false; } return true;}// function to find the maximum sum of a continuous subarray that contains only prime integersfunction maxPrimeSubarraySum(arr) { let n = arr.length; let maxSum = 0; for (let i = 0; i < n; i++) { let currentSum = 0; for (let j = i; j < n; j++) { if (isPrime(arr[j])) { // if integer is prime, add it to the current sum and update max sum if necessary currentSum += arr[j]; maxSum = Math.max(maxSum, currentSum); } else { // if integer is not prime, break and move to next subarray break; } } } return maxSum;}let arr = [1, 3, 5, 6, 7];let sum = maxPrimeSubarraySum(arr);console.log("Maximum sum of prime subarray is: " + sum); |
Output
Maximum sum of prime subarray is: 8
Time Complexity: O(N^2*sqrt(N)), since we are checking all possible subarrays and then checking if each integer in the subarray is prime.
Auxiliary Space: O(1), since we are not using any additional data structures.
Efficient Approach: To solve the problem using Hashmap follow the below steps:
- Inside the maxPrimeSubarraySum function, we initialize the variables maxSum, currentSum, start, and end.
- We then loop through the input array arr, incrementing the end variable each time.
- If the current element of arr is prime, we add it to currentSum, update maxSum if currentSum is greater, and move the start pointer forward.
- If the current element of arr is not prime, we subtract the prime integers from currentSum until the current element is no longer included in the subarray.
- We repeat steps 5-6 until we have looped through the entire array.
- Finally, we return the maxSum.
Below is the code to implement the above steps:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a number is primebool isPrime(int n){ if (n <= 1) // 1 is not prime return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) // If n is divisible by i, // it's not prime return false; } return true;}// Function to find the maximum sum of a// continuous subarray such that the// subarray only contains prime integersint maxPrimeSubarraySum(int arr[], int n){ unordered_map<int, int> freq; // Map to store frequency of elements int maxSum = 0, currentSum = 0; // Variables to store maximum sum // and current sum for (int i = 0; i < n; i++) { if (isPrime(arr[i])) // If the element is prime { currentSum += arr[i]; // Add it to the current sum freq[arr[i]]++; // Increment its frequency in // the map while (freq[arr[i]] > 1) // If the element is not unique { // Remove the non-unique // elements from the // current sum and map freq[arr[i - freq[arr[i]] + 1]]--; currentSum -= arr[i - freq[arr[i]] + 1]; } maxSum = max(maxSum, currentSum); // Update maximum sum } else // If the element is not prime { freq.clear(); // Reset the frequency map currentSum = 0; // Reset the current sum } } return maxSum; // Return the maximum sum of a // subarray with unique // prime integers}// Driver's codeint main(){ int arr[] = { 1, 3, 5, 6, 7 }; // Sample input array int n = sizeof(arr) / sizeof(arr[0]); // Size of the input array int sum = maxPrimeSubarraySum(arr, n); // Find the maximum sum of a subarray // with unique prime integers cout << "Maximum sum of prime subarray is: " << sum << endl; // Print the result return 0;} |
Java
import java.util.HashMap;import java.util.Map;public class Main { // Function to check if a number is prime public static boolean isPrime(int n) { if (n <= 1) // 1 is not prime return false; for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) // If n is divisible by i, it's // not prime return false; } return true; } // Function to find the maximum sum of a continuous // subarray such that the subarray only contains prime // integers public static int maxPrimeSubarraySum(int[] arr, int n) { Map<Integer, Integer> freq = new HashMap<>(); // Map to store frequency of // elements int maxSum = 0, currentSum = 0; // Variables to store maximum // sum and current sum for (int i = 0; i < n; i++) { if (isPrime( arr[i])) { // If the element is prime currentSum += arr[i]; // Add it to the current sum freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1); // Increment its // frequency in the map while ( freq.get(arr[i]) > 1) { // If the element is not unique // Remove the non-unique elements from // the current sum and map freq.put( arr[i - freq.get(arr[i]) + 1], freq.get( arr[i - freq.get(arr[i]) + 1]) - 1); currentSum -= arr[i - freq.get(arr[i]) + 1]; } maxSum = Math.max( maxSum, currentSum); // Update maximum sum } else { // If the element is not prime freq.clear(); // Reset the frequency map currentSum = 0; // Reset the current sum } } return maxSum; // Return the maximum sum of a // subarray with unique prime // integers } // Driver's code public static void main(String[] args) { int[] arr = { 1, 3, 5, 6, 7 }; // Sample input array int n = arr.length; // Size of the input array int sum = maxPrimeSubarraySum( arr, n); // Find the maximum sum of a subarray // with unique prime integers System.out.println( "Maximum sum of prime subarray is: " + sum); // Print the result }} |
Python3
import math# Function to check if a number is primedef isPrime(n): if n <= 1: # 1 is not prime return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: # If n is divisible by i, it's not prime return False return True# Function to find the maximum sum of a continuous subarray# such that the subarray only contains prime integersdef maxPrimeSubarraySum(arr): freq = {} # Dictionary to store frequency of elements maxSum = 0 # Variable to store maximum sum currentSum = 0 # Variable to store current sum for i in range(len(arr)): if isPrime(arr[i]): # If the element is prime currentSum += arr[i] # Add it to the current sum if arr[i] in freq: freq[arr[i]] += 1 # Increment its frequency in the dictionary else: freq[arr[i]] = 1 while freq[arr[i]] > 1: # If the element is not unique # Remove the non-unique elements from the current sum and dictionary freq[arr[i - freq[arr[i]] + 1]] -= 1 currentSum -= arr[i - freq[arr[i]] + 1] maxSum = max(maxSum, currentSum) # Update maximum sum else: # If the element is not prime freq = {} # Reset the frequency dictionary currentSum = 0 # Reset the current sum return maxSum # Return the maximum sum of a subarray with unique prime integersarr = [1, 3, 5, 6, 7] # Sample input array# Find the maximum sum of a subarray with unique prime integerssum = maxPrimeSubarraySum(arr)print("Maximum sum of prime subarray is:", sum) # Print the result |
C#
using System;using System.Collections.Generic;class Program{ // Function to check if a number is prime static bool IsPrime(int n) { if (n <= 1) // 1 is not prime return false; for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // If n is divisible by i, // it's not prime return false; } } return true; } // Function to find the maximum sum of a // continuous subarray such that the // subarray only contains prime integers static int MaxPrimeSubarraySum(int[] arr, int n) { Dictionary<int, int> freq = new Dictionary<int, int>(); // Dictionary to store frequency of elements int maxSum = 0, currentSum = 0; // Variables to store maximum sum // and current sum for (int i = 0; i < n; i++) { if (IsPrime(arr[i])) { // If the element is prime currentSum += arr[i]; // Add it to the current sum if (!freq.ContainsKey(arr[i])) { freq[arr[i]] = 0; } freq[arr[i]]++; // Increment its frequency in the dictionary while (freq[arr[i]] > 1) { // If the element is not unique // Remove the non-unique elements from the // current sum and dictionary freq[arr[i - freq[arr[i]] + 1]]--; currentSum -= arr[i - freq[arr[i]] + 1]; } maxSum = Math.Max(maxSum, currentSum); // Update maximum sum } else { // If the element is not prime freq.Clear(); // Reset the frequency dictionary currentSum = 0; // Reset the current sum } } return maxSum; // Return the maximum sum of a // subarray with unique prime integers } // Driver's code static void Main(string[] args) { int[] arr = { 1, 3, 5, 6, 7 }; // Sample input array int n = arr.Length; // Size of the input array int sum = MaxPrimeSubarraySum(arr, n); // Find the maximum sum of a subarray // with unique prime integers Console.WriteLine("Maximum sum of prime subarray is: " + sum); // Print the result }}// Contributed by Aditi Tyagi |
Javascript
// Function to check if a number is primefunction isPrime(n) { if (n <= 1) { // 1 is not prime return false; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { // If n is divisible by i, it's not prime return false; } } return true;}// Function to find the maximum sum of a continuous subarray// such that the subarray only contains prime integersfunction maxPrimeSubarraySum(arr) { const freq = new Map(); // Map to store frequency of elements let maxSum = 0, currentSum = 0; // Variables to store maximum sum and current sum for (let i = 0; i < arr.length; i++) { if (isPrime(arr[i])) { // If the element is prime currentSum += arr[i]; // Add it to the current sum freq.set(arr[i], (freq.get(arr[i]) || 0) + 1); // Increment its frequency in the map while (freq.get(arr[i]) > 1) { // If the element is not unique // Remove the non-unique elements from the current sum and map freq.set(arr[i - freq.get(arr[i]) + 1], freq.get(arr[i] - 1)); currentSum -= arr[i - freq.get(arr[i]) + 1]; } maxSum = Math.max(maxSum, currentSum); // Update maximum sum } else { // If the element is not prime freq.clear(); // Reset the frequency map currentSum = 0; // Reset the current sum } } return maxSum; // Return the maximum sum of a subarray with unique prime integers}const arr = [1, 3, 5, 6, 7]; // Sample input arrayconst sum = maxPrimeSubarraySum(arr); // Find the maximum sum of a subarray with unique prime integersconsole.log("Maximum sum of prime subarray is:", sum); // Print the result |
Output
Maximum sum of prime subarray is: 8
Time Complexity: O(N*sqrt(N)) because the function uses a single pass of the input array, and the operations performed in each iteration use sqrt(N) time in the prime function.
Auxiliary Space: O(N), because we used a hash map to store the indices of the unique prime numbers, encountered so far, and the hash table can potentially store all n elements of the input array.
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!
Share your thoughts in the comments
