Length of longest subarray having only K distinct Prime Numbers
Given an array arr[] consisting of N positive integers. The task is to find the length of the longest subarray of this array that contains exactly K distinct Prime Numbers. If there doesn’t exist any subarray, then print “-1”.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, K = 1
Output: 4
Explanation:
The subarray {6, 7, 8, 9} contains 4 elements and only one is prime (7). Therefore, the required length is 4.Input: arr[] = {1, 2, 3, 3, 4, 5, 6, 7, 8, 9}, K = 3
Output: 8
Explanation:
The subarray {3, 3, 4, 5, 6, 7, 8, 9} contains 8 elements and contains only 3 distinct primes(3, 5, and 7). Therefore, the required length is 8.
Naive Approach: The idea is to generate all possible subarray and check if any subarray with maximum length contains K distinct primes. If yes, then print that length of the subarray, else print “-1”.
Time Complexity: O(N2), where N is the length of the given array.
Space Complexity: O(N)
Efficient Approach: The idea is to use the Sieve of Eratosthenes to calculate the prime numbers and the Two Pointer Technique to solve the above problem. Below are the steps:
- Pre-calculate whether the given number is prime or not using the Sieve of Eratosthenes.
- Maintain the count of primes occurring in the given array while traversing it.
- Until K is not zero, we count the distinct prime occurring in the subarray and decrease K by 1.
- As K becomes negative, start deleting the elements till the first prime number of the current subarray as there might be a possibility of a longer subarray afterward.
- When K is 0, we update the maximum length.
- Print the maximum length after all the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; bool isprime[2000010]; // Function to precalculate all the // prime up to 10^6 void SieveOfEratosthenes( int n) { // Initialize prime to true memset (isprime, true , sizeof (isprime)); isprime[1] = false ; // Iterate [2, sqrt(N)] for ( int p = 2; p * p <= n; p++) { // If p is prime if (isprime[p] == true ) { // Mark all multiple of p as true for ( int i = p * p; i <= n; i += p) isprime[i] = false ; } } } // Function that finds the length of // longest subarray K distinct primes int KDistinctPrime( int arr[], int n, int k) { // Precompute all prime up to 2*10^6 SieveOfEratosthenes(2000000); // Keep track occurrence of prime map< int , int > cnt; // Initialize result to -1 int result = -1; for ( int i = 0, j = -1; i < n; ++i) { int x = arr[i]; // If number is prime then // increment its count and // decrease k if (isprime[x]) { if (++cnt[x] == 1) { // Decrement K --k; } } // Remove required elements // till k become non-negative while (k < 0) { x = arr[++j]; if (isprime[x]) { // Decrease count so // that it may appear // in another subarray // appearing after this // present subarray if (--cnt[x] == 0) { // Increment K ++k; } } } // Take the max value as // length of subarray if (k == 0) result = max(result, i - j); } // Return the final length return result; } // Driver Code int main( void ) { // Given array arr[] int arr[] = { 1, 2, 3, 3, 4, 5, 6, 7, 8, 9 }; int K = 3; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << KDistinctPrime(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ static boolean [] isprime = new boolean [ 2000010 ]; // Function to precalculate all the // prime up to 10^6 static void SieveOfEratosthenes( int n) { // Initialize prime to true Arrays.fill(isprime, true ); isprime[ 1 ] = false ; // Iterate [2, sqrt(N)] for ( int p = 2 ; p * p <= n; p++) { // If p is prime if (isprime[p] == true ) { // Mark all multiple of p as true for ( int i = p * p; i <= n; i += p) isprime[i] = false ; } } } // Function that finds the length of // longest subarray K distinct primes static int KDistinctPrime( int arr[], int n, int k) { // Precompute all prime up to 2*10^6 SieveOfEratosthenes( 2000000 ); // Keep track occurrence of prime Map<Integer, Integer> cnt = new HashMap<>(); // Initialize result to -1 int result = - 1 ; for ( int i = 0 , j = - 1 ; i < n; ++i) { int x = arr[i]; // If number is prime then // increment its count and // decrease k if (isprime[x]) { cnt.put(x, cnt.getOrDefault(x, 0 ) + 1 ); if (cnt.get(x) == 1 ) { // Decrement K --k; } } // Remove required elements // till k become non-negative while (k < 0 ) { x = arr[++j]; if (isprime[x]) { // Decrease count so // that it may appear // in another subarray // appearing after this // present subarray cnt.put(x, cnt.getOrDefault(x, 0 ) - 1 ); if (cnt.get(x) == 0 ) { // Increment K ++k; } } } // Take the max value as // length of subarray if (k == 0 ) result = Math.max(result, i - j); } // Return the final length return result; } // Driver Code public static void main (String[] args) { // Given array arr[] int arr[] = { 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; int K = 3 ; int N = arr.length; // Function call System.out.println(KDistinctPrime(arr, N, K)); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach from collections import defaultdict isprime = [ True ] * 2000010 # Function to precalculate all the # prime up to 10^6 def SieveOfEratosthenes(n): isprime[ 1 ] = False # Iterate [2, sqrt(N)] p = 2 while (p * p < = n): # If p is prime if (isprime[p] = = True ): # Mark all multiple of p as true for i in range (p * p, n + 1 , p): isprime[i] = False p + = 1 # Function that finds the length of # longest subarray K distinct primes def KDistinctPrime(arr, n, k): # Precompute all prime up to 2*10^6 SieveOfEratosthenes( 2000000 ) # Keep track occurrence of prime cnt = defaultdict( lambda : 0 ) # Initialize result to -1 result = - 1 j = - 1 for i in range (n): x = arr[i] # If number is prime then # increment its count and # decrease k if (isprime[x]): cnt[x] + = 1 if (cnt[x] = = 1 ): # Decrement K k - = 1 # Remove required elements # till k become non-negative while (k < 0 ): j + = 1 x = arr[j] if (isprime[x]): # Decrease count so # that it may appear # in another subarray # appearing after this # present subarray cnt[x] - = 1 if (cnt[x] = = 0 ): # Increment K k + = 1 # Take the max value as # length of subarray if (k = = 0 ): result = max (result, i - j) # Return the final length return result # Driver Code # Given array arr[] arr = [ 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] K = 3 N = len (arr) # Function call print (KDistinctPrime(arr, N, K)) # This code is contributed by Shivam Singh |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ static bool [] isprime = new bool [2000010]; // Function to precalculate all the // prime up to 10^6 static void SieveOfEratosthenes( int n) { // Initialize prime to true for ( int i = 0; i < isprime.Length; i++) isprime[i] = true ; isprime[1] = false ; // Iterate [2, sqrt(N)] for ( int p = 2; p * p <= n; p++) { // If p is prime if (isprime[p] == true ) { // Mark all multiple of p as true for ( int i = p * p; i <= n; i += p) isprime[i] = false ; } } } // Function that finds the length of // longest subarray K distinct primes static int KDistinctPrime( int []arr, int n, int k) { // Precompute all prime up to 2*10^6 SieveOfEratosthenes(2000000); // Keep track occurrence of prime Dictionary< int , int > cnt = new Dictionary< int , int >(); // Initialize result to -1 int result = -1; for ( int i = 0, j = -1; i < n; ++i) { int x = arr[i]; // If number is prime then // increment its count and // decrease k if (isprime[x]) { if (cnt.ContainsKey(x)) cnt[x] = cnt[x] + 1; else cnt.Add(x, 1); if (cnt[x] == 1) { // Decrement K --k; } } // Remove required elements // till k become non-negative while (k < 0) { x = arr[++j]; if (isprime[x]) { // Decrease count so // that it may appear // in another subarray // appearing after this // present subarray if (cnt.ContainsKey(x)) cnt[x] = cnt[x] - 1; else cnt.Add(x, 0); if (cnt[x] == 0) { // Increment K ++k; } } } // Take the max value as // length of subarray if (k == 0) result = Math.Max(result, i - j); } // Return the readonly length return result; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = {1, 2, 3, 3, 4, 5, 6, 7, 8, 9}; int K = 3; int N = arr.Length; // Function call Console.WriteLine(KDistinctPrime(arr, N, K)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach let isprime = new Array(2000010); // Function to precalculate all the // prime up to 10^6 function SieveOfEratosthenes(n) { // Initialize prime to true isprime.fill( true ); isprime[1] = false ; // Iterate [2, sqrt(N)] for (let p = 2; p * p <= n; p++) { // If p is prime if (isprime[p] == true ) { // Mark all multiple of p as true for (let i = p * p; i <= n; i += p) isprime[i] = false ; } } } // Function that finds the length of // longest subarray K distinct primes function KDistinctPrime(arr, n, k) { // Precompute all prime up to 2*10^6 SieveOfEratosthenes(2000000); // Keep track occurrence of prime let cnt = new Map(); // Initialize result to -1 let result = -1; for (let i = 0, j = -1; i < n; ++i) { let x = arr[i]; // If number is prime then // increment its count and // decrease k if (isprime[x]) { if (cnt.has(x)) cnt.set(x, cnt.get(x)+1) else cnt.set(x, 1); if (cnt.get(x) == 1) { // Decrement K --k; } } // Remove required elements // till k become non-negative while (k < 0) { x = arr[++j]; if (isprime[x]) { // Decrease count so // that it may appear // in another subarray // appearing after this // present subarray if (cnt.has(x)) cnt.set(x, cnt.get(x) - 1) else cnt.set(x, -1); if (cnt.get(x) == 0) { // Increment K ++k; } } } // Take the max value as // length of subarray if (k == 0) result = Math.max(result, i - j); } // Return the final length return result; } // Given array arr[] let arr = [ 1, 2, 3, 3, 4, 5, 6, 7, 8, 9 ]; let K = 3; let N = arr.length; // Function call document.write(KDistinctPrime(arr, N, K)); </script> |
8
Time Complexity: O(N*log(log(N))), where N is the maximum element in the given array.
Auxiliary Space: O(N)
Another Method (sliding window approach)
The task is to find the length of the longest subarray of this array can be found out using sliding window approach
Algorithm
- Initialize variables count, left, and max_len to 0
- Precompute all prime numbers up to the largest number in the array
- Iterate over each element in the array from left to right:
- If the current element is prime, increment the count of that prime in the count dictionary
- If the count of distinct primes in the count dictionary is greater than K, move the left pointer to the right until the count is less than or equal to K
- If the count of distinct primes in the count dictionary is equal to K, update max_len with the length of the current subarray (right – left + 1)
- Return max_len if it is greater than 0, Else return -1
C++
//C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if N is prime or not bool isPrime( int n, const vector< int >& primes) { // Check if n is prime using the // precomputed list of primes for ( int p : primes) { if (p * p > n) break ; if (n % p == 0) return false ; } return n > 1; } // Function to find the longest subarray // with K primes int longestSubarrayWithKPrimes( const std::vector< int >& arr, int k) { // Precompute all primes up to // the largest number in the array int limit = *std::max_element(arr.begin(), arr.end()); std::vector< int > primes; for ( int p = 2; p <= limit; p++) { if (isPrime(p, primes)) primes.push_back(p); } // Initialize variables std::unordered_map< int , int > count; int left = 0; int maxLen = -1; // Move the window to the right until // we find a window with K distinct primes for ( int right = 0; right < arr.size(); right++) { if (isPrime(arr[right], primes)) count[arr[right]] += 1; while (count.size() > k) { if (isPrime(arr[left], primes)) { count[arr[left]] -= 1; if (count[arr[left]] == 0) count.erase(arr[left]); } left++; } if (count.size() == k) maxLen = std::max(maxLen, right - left + 1); } return maxLen; } // Driver Code int main() { vector< int > arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int k = 1; cout << longestSubarrayWithKPrimes(arr, k) << endl; // Output: 4 arr = {1, 2, 3, 3, 4, 5, 6, 7, 8, 9}; k = 3; cout << longestSubarrayWithKPrimes(arr, k) << endl; // Output: 8 return 0; } // This code is contributed by Utkarsh Kumar |
Java
//Java program for the above approach import java.util.*; class GFG { // Function to check if N is prime or not static boolean isPrime( int n, List<Integer> primes) { // Check if n is prime using the // precomputed list of primes for ( int p : primes) { if (p * p > n) break ; if (n % p == 0 ) return false ; } return n > 1 ; } // Function to find the longest subarray // with K primes static int longestSubarrayWithKPrimes(List<Integer> arr, int k) { // Precompute all primes up to // the largest number in the array int limit = Collections.max(arr); List<Integer> primes = new ArrayList<>(); for ( int p = 2 ; p <= limit; p++) { if (isPrime(p, primes)) primes.add(p); } // Initialize variables Map<Integer, Integer> count = new HashMap<>(); int left = 0 ; int maxLen = - 1 ; // Move the window to the right until // we find a window with K distinct primes for ( int right = 0 ; right < arr.size(); right++) { if (isPrime(arr.get(right), primes)) count.put(arr.get(right), count.getOrDefault(arr.get(right), 0 ) + 1 ); while (count.size() > k) { if (isPrime(arr.get(left), primes)) { count.put(arr.get(left), count.get(arr.get(left)) - 1 ); if (count.get(arr.get(left)) == 0 ) count.remove(arr.get(left)); } left++; } if (count.size() == k) maxLen = Math.max(maxLen, right - left + 1 ); } return maxLen; } // Driver Code public static void main(String[] args) { List<Integer> arr = Arrays.asList( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ); int k = 1 ; System.out.println(longestSubarrayWithKPrimes(arr, k)); // Output: 4 arr = Arrays.asList( 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ); k = 3 ; System.out.println(longestSubarrayWithKPrimes(arr, k)); // Output: 8 } } // This code is contributed by Pushpesh Raj. |
Python3
# Python program for the above approach # Function to check if N is prime or not def is_prime(n, primes): # Check if n is prime using the # precomputed list of primes for p in primes: if p * p > n: break if n % p = = 0 : return False return n > 1 # Function to find the longest subarray # with K primes def longest_subarray_with_k_primes(arr, k): # Precompute all primes up to # the largest number in the array limit = max (arr) primes = [p for p in range ( 2 , limit + 1 ) if is_prime(p, primes = [])] # Initialize variables count = {} left = 0 max_len = - 1 # Move the window to the right until # we find a window with K distinct primes for right in range ( len (arr)): if is_prime(arr[right], primes): count[arr[right]] = count.get(arr[right], 0 ) + 1 while len (count) > k: if is_prime(arr[left], primes): count[arr[left]] - = 1 if count[arr[left]] = = 0 : del count[arr[left]] left + = 1 if len (count) = = k: max_len = max (max_len, right - left + 1 ) return max_len # Driver Code arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] k = 1 print (longest_subarray_with_k_primes(arr, k)) # Output: 4 arr = [ 1 , 2 , 3 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] k = 3 print (longest_subarray_with_k_primes(arr, k)) # Output: 8 |
C#
using System; using System.Collections.Generic; using System.Linq; class GFG { // Function to check if N is prime or not static bool IsPrime( int n, List< int > primes) { // Check if n is prime using the // precomputed list of primes foreach ( int p in primes) { if (p * p > n) break ; if (n % p == 0) return false ; } return n > 1; } // Function to find the longest subarray // with K primes static int LongestSubarrayWithKPrimes(List< int > arr, int k) { // Precompute all primes up to // the largest number in the array int limit = arr.Max(); List< int > primes = new List< int >(); for ( int p = 2; p <= limit; p++) { if (IsPrime(p, primes)) primes.Add(p); } // Initialize variables Dictionary< int , int > count = new Dictionary< int , int >(); int left = 0; int maxLen = -1; // Move the window to the right until // we find a window with K distinct primes for ( int right = 0; right < arr.Count; right++) { if (IsPrime(arr[right], primes)) count[arr[right]] = count.GetValueOrDefault(arr[right]) + 1; while (count.Count > k) { if (IsPrime(arr[left], primes)) { count[arr[left]] -= 1; if (count[arr[left]] == 0) count.Remove(arr[left]); } left++; } if (count.Count == k) maxLen = Math.Max(maxLen, right - left + 1); } return maxLen; } // Driver Code static void Main() { List< int > arr = new List< int >{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int k = 1; Console.WriteLine(LongestSubarrayWithKPrimes( arr, k)); // Output: 4 arr = new List< int >{ 1, 2, 3, 3, 4, 5, 6, 7, 8, 9 }; k = 3; Console.WriteLine(LongestSubarrayWithKPrimes( arr, k)); // Output: 8 } } |
Javascript
// Function to check if N is prime or not function isPrime(n, primes) { for (let p of primes) { if (p * p > n) break ; if (n % p === 0) return false ; } return n > 1; } // Function to find the longest subarray with K primes function longestSubarrayWithKPrimes(arr, k) { let limit = Math.max(...arr); // Find the largest number in the array let primes = []; // Precompute prime numbers up to the limit for (let p = 2; p <= limit; p++) { if (isPrime(p, primes)) primes.push(p); } let count = new Map(); // Map to keep track of occurrences of prime elements let left = 0; // Left pointer of the sliding window let maxLen = -1; // Length of the longest subarray with K primes for (let right = 0; right < arr.length; right++) { if (isPrime(arr[right], primes)) { if (!count.has(arr[right])) { count.set(arr[right], 0); // Initialize count for a new prime element } count.set(arr[right], count.get(arr[right]) + 1); // Increment count for the prime element } // Contract the window from the left until only K distinct primes are present while (count.size > k) { if (isPrime(arr[left], primes)) { count.set(arr[left], count.get(arr[left]) - 1); // Decrement count for the prime element if (count.get(arr[left]) === 0) count. delete (arr[left]); // Remove element from the map if count becomes 0 } left++; // Move the left pointer to contract the window } // Update the maxLen if the current window has K distinct primes if (count.size === k) maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } // Driver Code let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; let k = 1; console.log(longestSubarrayWithKPrimes(arr, k)); // Output: 4 arr = [1, 2, 3, 3, 4, 5, 6, 7, 8, 9]; k = 3; console.log(longestSubarrayWithKPrimes(arr, k)); // Output: 8 |
4 8
Time Complexity: O(N * log(log(max(arr))) + N2), where N is the length of the input array and max(arr) is the maximum element in the array.
Space Complexity: O(max(arr)), due to the count dictionary used to store the count of each prime number in the subarray.