Given an array A of integers. We can remove at most one index from the array. Our goal is to maximize the length of the subarray that contains all primes. Print the largest length subarray that you can achieve by removing exactly one element from the array .
Examples:
Input : arr[] = { 2, 8, 5, 7, 9, 5, 7 }
Output : 4Explanation : If we remove the number 9 which is at index 5 then the remaining array contains a subarray whose length is 4 which is maximum.
Input : arr[] = { 2, 3, 5, 7 }
Output : 3If we remove the number 3 which is at index 1 then the remaining array contains a subarray whose length is 3 which is maximum.
The idea is to count contiguous primes just before every index and just after every index. Now traverse the array again and find an index for which sum counts of primes after and before is maximum.
Implementation:
C++
// CPP program to find length of the longest// subarray with all primes except possibly// one.#include <bits/stdc++.h>using namespace std;#define N 100000bool prime[N];void SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= N; i += p) prime[i] = false; } }}int longestPrimeSubarray(int arr[], int n){ int left[n], right[n]; int primecount = 0, res = 0; // left array used to count number of // continuous prime numbers starting // from left of current element for (int i = 0; i < n; i++) { left[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } // right array used to count number of // continuous prime numbers starting from // right of current element primecount = 0; for (int i = n - 1; i >= 0; i--) { right[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } for (int i = 0; i < n; i++) res = max(res, left[i] + right[i]); return res;}// Driver codeint main(){ int arr[] = { 2, 8, 5, 7, 9, 5, 7 }; // used of SieveOfEratosthenes method to // detect a number prime or not SieveOfEratosthenes(); int n = sizeof(arr) / sizeof(arr[0]); cout << "largest length of PrimeSubarray " << longestPrimeSubarray(arr, n) << endl; return 0;} |
Java
// Java program to find length of the longest// subarray with all primes except possibly// one.import java.util.*;class GFG{ static int N = 100000;static boolean prime[] = new boolean[N];static void SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. Arrays.fill(prime,true); for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < N; i += p) prime[i] = false; } }}static int longestPrimeSubarray(int arr[], int n){ int []left = new int[n];int[] right = new int[n]; int primecount = 0, res = 0; // left array used to count number of // continuous prime numbers starting // from left of current element for (int i = 0; i < n; i++) { left[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } // right array used to count number of // continuous prime numbers starting from // right of current element primecount = 0; for (int i = n - 1; i >= 0; i--) { right[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } for (int i = 0; i < n; i++) res = Math.max(res, left[i] + right[i]); return res;}// Driver codepublic static void main(String[] args) { int arr[] = { 2, 8, 5, 7, 9, 5, 7 }; // used of SieveOfEratosthenes method to // detect a number prime or not SieveOfEratosthenes(); int n = arr.length; System.out.println("largest length of PrimeSubarray " + longestPrimeSubarray(arr, n));}}// This code contributed by Rajput-Ji |
Python3
# Python 3 program to find length of the # longest subarray with all primes except # possibly one.from math import sqrtN = 100000prime = [True for i in range(N + 1)]def SieveOfEratosthenes(): # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. k = int(sqrt(N)) + 1 for p in range(2, k, 1): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * 2, N + 1, p): prime[i] = False def longestPrimeSubarray(arr, n): left = [0 for i in range(n)] right = [0 for i in range(n)] primecount = 0 res = 0 # left array used to count number of # continuous prime numbers starting # from left of current element for i in range(n): left[i] = primecount if (prime[arr[i]]): primecount += 1 else: primecount = 0 # right array used to count number of # continuous prime numbers starting # from right of current element primecount = 0 i = n - 1 while(i >= 0): right[i] = primecount if (prime[arr[i]]): primecount += 1 else: primecount = 0 i -= 1 for i in range(n): res = max(res, left[i] + right[i]) return res# Driver codeif __name__ == '__main__': arr = [2, 8, 5, 7, 9, 5, 7] # used of SieveOfEratosthenes method # to detect a number prime or not SieveOfEratosthenes() n = len(arr) print("largest length of PrimeSubarray", longestPrimeSubarray(arr, n)) # This code is contributed by# Surendra_Gangwar |
C#
// C# program to find length of the longest// subarray with all primes except possibly// one.using System;class GFG{ static int N = 100000; static bool []prime = new bool[N]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. for(int i =0;i<N;i++) prime[i]=true; for (int p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < N; i += p) prime[i] = false; } } } static int longestPrimeSubarray(int []arr, int n) { int []left = new int[n];int[] right = new int[n]; int primecount = 0, res = 0; // left array used to count number of // continuous prime numbers starting // from left of current element for (int i = 0; i < n; i++) { left[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } // right array used to count number of // continuous prime numbers starting from // right of current element primecount = 0; for (int i = n - 1; i >= 0; i--) { right[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } for (int i = 0; i < n; i++) res = Math.Max(res, left[i] + right[i]); return res; } // Driver code public static void Main(String[] args) { int []arr = { 2, 8, 5, 7, 9, 5, 7 }; // used of SieveOfEratosthenes method to // detect a number prime or not SieveOfEratosthenes(); int n = arr.Length; Console.WriteLine("largest length of PrimeSubarray " + longestPrimeSubarray(arr, n)); }}// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP program to find length of // the longest subarray with all at most// primes except possibly one.$N = 100000;$prime = array_fill(0, $N, true);function SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" // and initialize all entries it as // true. A value in prime[i] will // finally be false if i is Not a // prime, else true. global $prime, $N; for ($p = 2; $p * $p <= $N; $p++) { // If prime[p] is not changed, // then it is a prime if ($prime[$p] == true) { // Update all multiples of p for ($i = $p * 2; $i <= $N; $i += $p) $prime[$i] = false; } }}function longestPrimeSubarray($arr, $n){ global $prime, $N; $left = array($n); $right = array($n); $primecount = 0; $res = 0; // left array used to count number of // continuous prime numbers starting // from left of current element for ($i = 0; $i < $n; $i++) { $left[$i] = $primecount; if ($prime[$arr[$i]]) { $primecount++; } else $primecount = 0; } // right array used to count number // of continuous prime numbers starting // from right of current element $primecount = 0; for ($i = $n - 1; $i >= 0; $i--) { $right[$i] = $primecount; if ($prime[$arr[$i]]) { $primecount++; } else $primecount = 0; } for ($i = 0; $i < $n; $i++) $res = max($res, $left[$i] + $right[$i]); return $res;}// Driver Code$arr = array(2, 8, 5, 7, 9, 5, 7);// used of SieveOfEratosthenes method // to detect a number prime or notSieveOfEratosthenes();$n = count($arr);echo "largest length of PrimeSubarray " . longestPrimeSubarray($arr, $n);// This code is contributed by mits?> |
Javascript
<script>// Javascript program to find length of the longest// subarray with all primes except possibly// one.var N = 100000;var prime = Array.from({length: N}, (_, i) => true);function SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. for (var p = 2; p * p <= N; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for(var i = p * 2; i < N; i += p) prime[i] = false; } }}function longestPrimeSubarray(arr , n){ var left = Array.from({length: n}, (_, i) => 0); var right = Array.from({length: n}, (_, i) => 0); var primecount = 0, res = 0; // Left array used to count number of // continuous prime numbers starting // from left of current element for(var i = 0; i < n; i++) { left[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } // Right array used to count number of // continuous prime numbers starting from // right of current element primecount = 0; for(var i = n - 1; i >= 0; i--) { right[i] = primecount; if (prime[arr[i]]) { primecount++; } else primecount = 0; } for(var i = 0; i < n; i++) res = Math.max(res, left[i] + right[i]); return res;}// Driver codevar arr = [ 2, 8, 5, 7, 9, 5, 7 ];// Used of SieveOfEratosthenes method to // detect a number prime or notSieveOfEratosthenes();var n = arr.length;document.write("largest length of PrimeSubarray " + longestPrimeSubarray(arr, n));// This code is contributed by shikhasingrajput </script> |
Output
largest length of PrimeSubarray 4
Time Complexity: O(N*log(log(N) + N)
Auxiliary Space: O(N)
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!
