Given an array arr[] of N integers and a number K. The task is to count the number of subarray with exactly K Prime Numbers.
Example:
Input: arr[] = {1, 2, 3, 4}, K = 2
Output: 4
Explanation:
Since total number of prime number in the array are 2. So the 4 subarray with 2 prime number are:
1. {2, 3}
2. {1, 2, 3}
3. {2, 3, 4}
4. {1, 2, 3, 4}
Input: arr[] = {2, 4, 5}, K = 3
Output: 0
Explanation:
Since total number of prime number in the array are 2 which is less than K(K = 3).
So there is no such subarray with K primes.
Approach:
- Traverse the given array arr[] and check whether the element is prime or not.
- If the current element is prime then change the value of array that index to 1, Else change the value at that index to 0.
- Now the given array is converted into Binary Array.
- Find the count of subarray with sum equals to K in the above Binary Array using the approach discussed in this article.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// A utility function to check if// the number n is prime or notbool isPrime(int n){ int i; // Base Cases if (n <= 1) return false; if (n <= 3) return true; // Check to skip middle five // numbers in below loop if (n % 2 == 0 || n % 3 == 0) { return false; } for (i = 5; i * i <= n; i += 6) { // If n is divisible by i & i+2 // then it is not prime if (n % i == 0 || n % (i + 2) == 0) { return false; } } return true;}// Function to find number of subarrays// with sum exactly equal to kint findSubarraySum(int arr[], int n, int K){ // STL map to store number of subarrays // starting from index zero having // particular value of sum. unordered_map<int, int> prevSum; int res = 0; // To store the sum of element traverse // so far int currsum = 0; for (int i = 0; i < n; i++) { // Add current element to currsum currsum += arr[i]; // If currsum = K, then a new // subarray is found if (currsum == K) { res++; } // If currsum > K then find the // no. of subarrays with sum // currsum - K and exclude those // subarrays if (prevSum.find(currsum - K) != prevSum.end()) res += (prevSum[currsum - K]); // Add currsum to count of // different values of sum prevSum[currsum]++; } // Return the final result return res;}// Function to count the subarray with K primesvoid countSubarray(int arr[], int n, int K){ // Update the array element for (int i = 0; i < n; i++) { // If current element is prime // then update the arr[i] to 1 if (isPrime(arr[i])) { arr[i] = 1; } // Else change arr[i] to 0 else { arr[i] = 0; } } // Function Call cout << findSubarraySum(arr, n, K);}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4 }; int K = 2; int N = sizeof(arr) / sizeof(arr[0]); // Function Call countSubarray(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // A utility function to check if // the number n is prime or not static boolean isPrime(int n) { int i; // Base Cases if (n <= 1) return false; if (n <= 3) return true; // Check to skip middle five // numbers in below loop if (n % 2 == 0 || n % 3 == 0) { return false; } for (i = 5; i * i <= n; i += 6) { // If n is divisible by i & i+2 // then it is not prime if (n % i == 0 || n % (i + 2) == 0) { return false; } } return true; } // Function to find number of subarrays // with sum exactly equal to k static int findSubarraySum(int arr[], int n, int K) { // STL map to store number of subarrays // starting from index zero having // particular value of sum. HashMap<Integer, Integer> prevSum = new HashMap<Integer, Integer>(); int res = 0; // To store the sum of element traverse // so far int currsum = 0; for (int i = 0; i < n; i++) { // Add current element to currsum currsum += arr[i]; // If currsum = K, then a new // subarray is found if (currsum == K) { res++; } // If currsum > K then find the // no. of subarrays with sum // currsum - K and exclude those // subarrays if (prevSum.containsKey(currsum - K)) { res += (prevSum.get(currsum - K)); } // Add currsum to count of // different values of sum if (prevSum.containsKey(currsum)) prevSum.put(currsum, prevSum.get(currsum) + 1); else prevSum.put(currsum, 1); } // Return the final result return res; } // Function to count the subarray with K primes static void countSubarray(int arr[], int n, int K) { // Update the array element for (int i = 0; i < n; i++) { // If current element is prime // then update the arr[i] to 1 if (isPrime(arr[i])) { arr[i] = 1; } // Else change arr[i] to 0 else { arr[i] = 0; } } // Function Call System.out.print(findSubarraySum(arr, n, K)); } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 3, 4 }; int K = 2; int N = arr.length; // Function Call countSubarray(arr, N, K); }}// This code contributed by Rajput-Ji |
Python3
# Python3 program for the above approachfrom math import sqrt# A utility function to check if# the number n is prime or notdef isPrime(n): # Base Cases if (n <= 1): return False if (n <= 3): return True # Check to skip middle five # numbers in below loop if (n % 2 == 0 or n % 3 == 0): return False for i in range(5,int(sqrt(n))+1,6): # If n is divisible by i & i+2 # then it is not prime if (n % i == 0 or n % (i + 2) == 0): return False return True# Function to find number of subarrays# with sum exactly equal to kdef findSubarraySum(arr,n,K): # STL map to store number of subarrays # starting from index zero having # particular value of sum. prevSum = {i:0 for i in range(100)} res = 0 # To store the sum of element traverse # so far currsum = 0 for i in range(n): # Add current element to currsum currsum += arr[i] # If currsum = K, then a new # subarray is found if (currsum == K): res += 1 # If currsum > K then find the # no. of subarrays with sum # currsum - K and exclude those # subarrays if (currsum - K) in prevSum: res += (prevSum[currsum - K]) # Add currsum to count of # different values of sum prevSum[currsum] += 1 # Return the final result return res# Function to count the subarray with K primesdef countSubarray(arr,n,K): # Update the array element for i in range(n): # If current element is prime # then update the arr[i] to 1 if (isPrime(arr[i])): arr[i] = 1 # Else change arr[i] to 0 else: arr[i] = 0 # Function Call print(findSubarraySum(arr, n, K))# Driver Codeif __name__ == '__main__': arr = [1, 2, 3, 4] K = 2 N = len(arr) # Function Call countSubarray(arr, N, K)# This code is contributed by Surendra_Gangwar |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// A utility function to check if// the number n is prime or notstatic bool isPrime(int n){ int i; // Base Cases if (n <= 1) return false; if (n <= 3) return true; // Check to skip middle five // numbers in below loop if (n % 2 == 0 || n % 3 == 0) { return false; } for(i = 5; i * i <= n; i += 6) { // If n is divisible by i & i+2 // then it is not prime if (n % i == 0 || n % (i + 2) == 0) { return false; } } return true;}// Function to find number of subarrays// with sum exactly equal to kstatic int findSubarraySum(int []arr, int n, int K) { // STL map to store number of subarrays // starting from index zero having // particular value of sum. Dictionary<int, int> prevSum = new Dictionary<int, int>(); int res = 0; // To store the sum of element traverse // so far int currsum = 0; for(int i = 0; i < n; i++) { // Add current element to currsum currsum += arr[i]; // If currsum = K, then a new // subarray is found if (currsum == K) { res++; } // If currsum > K then find the // no. of subarrays with sum // currsum - K and exclude those // subarrays if (prevSum.ContainsKey(currsum - K)) { res += (prevSum[currsum - K]); } // Add currsum to count of // different values of sum if (prevSum.ContainsKey(currsum)) { prevSum[currsum] = prevSum[currsum] + 1; } else { prevSum.Add(currsum, 1); } } // Return the readonly result return res;}// Function to count the subarray with K primesstatic void countSubarray(int []arr, int n, int K){ // Update the array element for(int i = 0; i < n; i++) { // If current element is prime // then update the arr[i] to 1 if (isPrime(arr[i])) { arr[i] = 1; } // Else change arr[i] to 0 else { arr[i] = 0; } } // Function Call Console.Write(findSubarraySum(arr, n, K));}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, 2, 3, 4 }; int K = 2; int N = arr.Length; // Function Call countSubarray(arr, N, K);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach// A utility function to check if// the number n is prime or notfunction isPrime(n){ let i; // Base Cases if (n <= 1) return false; if (n <= 3) return true; // Check to skip middle five // numbers in below loop if (n % 2 == 0 || n % 3 == 0) { return false; } for (i = 5; i * i <= n; i += 6) { // If n is divisible by i & i+2 // then it is not prime if (n % i == 0 || n % (i + 2) == 0) { return false; } } return true;}// Function to find number of subarrays// with sum exactly equal to kfunction findSubarraySum(arr, n, K){ // STL map to store number of subarrays // starting from index zero having // particular value of sum. let prevSum = new Map(); let res = 0; // To store the sum of element traverse // so far let currsum = 0; for (let i = 0; i < n; i++) { // Add current element to currsum currsum += arr[i]; // If currsum = K, then a new // subarray is found if (currsum == K) { res++; } // If currsum > K then find the // no. of subarrays with sum // currsum - K and exclude those // subarrays if (prevSum.has(currsum - K)) res += (prevSum.get(currsum - K)); // Add currsum to count of // different values of sum if(prevSum.has(currsum)){ prevSum.set(currsum, prevSum.get(currsum) + 1) }else{ prevSum.set(currsum, 1) } } // Return the final result return res;}// Function to count the subarray with K primesfunction countSubarray(arr, n, K){ // Update the array element for (let i = 0; i < n; i++) { // If current element is prime // then update the arr[i] to 1 if (isPrime(arr[i])) { arr[i] = 1; } // Else change arr[i] to 0 else { arr[i] = 0; } } // Function Call document.write(findSubarraySum(arr, n, K));}// Driver Codelet arr = [ 1, 2, 3, 4 ];let K = 2;let N = arr.length;// Function CallcountSubarray(arr, N, K);// This code is contributed by _saurabh_jaiswal</script> |
Output:
4
Time Complexity: O(N*log(log(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!
