Given an array ‘arr’ of length ‘n’. The task is to find the largest contiguous sub-array having the count of prime numbers strictly greater than the count of non-prime numbers.
Examples:
Input: arr[] = {4, 7, 4, 7, 11, 5, 4, 4, 4, 5}
Output: 9
Input: arr[] = { 1, 9, 3, 4, 5, 6, 7, 8 }
Output: 5
Approach: To find the largest subarray in which count of prime is strictly greater than the count of non-prime:
First of all, use sieve to find the prime number.
Replace all primes with 1 in the array and all non-primes with -1. Now this problem is similar to Longest subarray having count of 1s one more than count of 0s
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;bool prime[1000000 + 5];void findPrime(){ memset(prime, true, sizeof(prime)); prime[1] = false; for (int p = 2; p * p <= 1000000; 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 <= 1000000; i += p) prime[i] = false; } }}// Function to find the length of longest// subarray having count of primes more// than count of non-primesint lenOfLongSubarr(int arr[], int n){ // unordered_map 'um' implemented as // hash table unordered_map<int, int> um; int sum = 0, maxLen = 0; // traverse the given array for (int i = 0; i < n; i++) { // consider -1 as non primes and 1 as primes sum += prime[arr[i]] == 0 ? -1 : 1; // when subarray starts form index '0' if (sum == 1) maxLen = i + 1; // make an entry for 'sum' if it is // not present in 'um' else if (um.find(sum) == um.end()) um[sum] = i; // check if 'sum-1' is present in 'um' // or not if (um.find(sum - 1) != um.end()) { // update maxLength if (maxLen < (i - um[sum - 1])) maxLen = i - um[sum - 1]; } } // required maximum length return maxLen;}// Driver codeint main(){ findPrime(); int arr[] = { 1, 9, 3, 4, 5, 6, 7, 8 }; int n = sizeof(arr) / sizeof(arr[0]); cout << lenOfLongSubarr(arr, n) << endl; return 0;} |
Java
// Java implementation of above approachimport java.util.*;class GfG { static boolean prime[] = new boolean[1000000 + 5]; static void findPrime() { Arrays.fill(prime, true); prime[1] = false; for (int p = 2; p * p <= 1000000; 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 <= 1000000; i += p) prime[i] = false; } } } // Function to find the length of longest // subarray having count of primes more // than count of non-primes static int lenOfLongSubarr(int arr[], int n) { // unordered_map 'um' implemented as // hash table Map<Integer, Integer> um = new HashMap<Integer, Integer>(); int sum = 0, maxLen = 0; // traverse the given array for (int i = 0; i < n; i++) { // consider -1 as non primes and 1 as primes sum += prime[arr[i]] == false ? -1 : 1; // when subarray starts form index '0' if (sum == 1) maxLen = i + 1; // make an entry for 'sum' if it is // not present in 'um' else if (!um.containsKey(sum)) um.put(sum, i); // check if 'sum-1' is present in 'um' // or not if (um.containsKey(sum - 1)) { // update maxLength if (maxLen < (i - um.get(sum - 1))) maxLen = i - um.get(sum - 1); } } // required maximum length return maxLen; } // Driver code public static void main(String[] args) { findPrime(); int arr[] = { 1, 9, 3, 4, 5, 6, 7, 8 }; int n = arr.length; System.out.println(lenOfLongSubarr(arr, n)); }} |
Python3
# Python3 implementation of above approach prime = [True] * (1000000 + 5) def findPrime(): prime[0], prime[1] = False, False for p in range(2, 1001): # 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, 1000001, p): prime[i] = False# Function to find the length of longest # subarray having count of primes more # than count of non-primes def lenOfLongSubarr(arr, n): # unordered_map 'um' implemented as # hash table um = {} Sum, maxLen = 0, 0 # traverse the given array for i in range(0, n): # consider -1 as non primes and 1 as primes Sum = Sum-1 if prime[arr[i]] == False else Sum + 1 # when subarray starts form index '0' if Sum == 1: maxLen = i + 1 # make an entry for 'sum' if # it is not present in 'um' elif Sum not in um: um[Sum] = i # check if 'sum-1' is present # in 'um' or not if (Sum - 1) in um: # update maxLength if maxLen < (i - um[Sum - 1]): maxLen = i - um[Sum - 1] # required maximum length return maxLen # Driver Codeif __name__ == "__main__": findPrime() arr = [1, 9, 3, 4, 5, 6, 7, 8] n = len(arr) print(lenOfLongSubarr(arr, n))# This code is contributed # by Rituraj Jain |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;class GfG { static bool[] prime = new bool[1000000 + 5]; static void findPrime() { Array.Fill(prime, true); prime[1] = false; for (int p = 2; p * p <= 1000000; 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 <= 1000000; i += p) prime[i] = false; } } } // Function to find the length of longest // subarray having count of primes more // than count of non-primes static int lenOfLongSubarr(int[] arr, int n) { // unordered_map 'um' implemented as // hash table Dictionary<int, int> um = new Dictionary<int, int>(); int sum = 0, maxLen = 0; // traverse the given array for (int i = 0; i < n; i++) { // consider -1 as non primes and 1 as primes sum += prime[arr[i]] == false ? -1 : 1; // when subarray starts form index '0' if (sum == 1) maxLen = i + 1; // make an entry for 'sum' if it is // not present in 'um' else if (!um.ContainsKey(sum)) um[sum] = i; // check if 'sum-1' is present in 'um' // or not if (um.ContainsKey(sum - 1)) { // update maxLength if (maxLen < (i - um[sum - 1])) maxLen = i - um[sum - 1]; } } // required maximum length return maxLen; } // Driver code public static void Main() { findPrime(); int[] arr = { 1, 9, 3, 4, 5, 6, 7, 8 }; int n = arr.Length; Console.WriteLine(lenOfLongSubarr(arr, n)); }}// This code is contributed by Code_Mech. |
Javascript
<script>// Javascript implementation of above approachlet prime = new Array(1000000 + 5);function findPrime() { prime.fill(true) prime[1] = false; for (let p = 2; p * p <= 1000000; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p for (let i = p * 2; i <= 1000000; i += p) prime[i] = false; } }}// Function to find the length of longest// subarray having count of primes more// than count of non-primesfunction lenOfLongSubarr(arr, n) { // unordered_map 'um' implemented as // hash table let um = new Map(); let sum = 0, maxLen = 0; // traverse the given array for (let i = 0; i < n; i++) { // consider -1 as non primes and 1 as primes sum += prime[arr[i]] == 0 ? -1 : 1; // when subarray starts form index '0' if (sum == 1) maxLen = i + 1; // make an entry for 'sum' if it is // not present in 'um' else if (!um.has(sum)) um.set(sum, i); // check if 'sum-1' is present in 'um' // or not if (um.has(sum - 1)) { // update maxLength if (maxLen < (i - um.get(sum - 1))) maxLen = i - um.get(sum - 1); } } // required maximum length return maxLen;}// Driver codefindPrime();let arr = [1, 9, 3, 4, 5, 6, 7, 8];let n = arr.length;document.write(lenOfLongSubarr(arr, n) + "<br>")// This code is contributed by Saurabh Jaiswal</script> |
Output:
5
Time Complexity: O(P*log(log(P)) + N), where P is the upper range up to which prime numbers are needed to be calculated during preprocessing and N is the length of the given array.
Auxiliary Space: O(P + N), where P is the hardcoded length of the prime array (1000000 + 5).
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!
