Given an integer K and an array arr[], the task is to find the number of subsequences from the given array such that each subsequence consists exactly K prime numbers.
Example:
Input: K = 2, arr = [2, 3, 4, 6]
Output: 4
Explanation:
There are 4 subsequences which consists exactly 2 prime numbers {2, 3} {2, 3, 4} {2, 3, 6} {2, 3, 4, 6}
Input: K = 3, arr = [1, 2, 3, 4, 5, 6, 7]
Output: 32
Explanation:
There are 32 subsequences which consists exactly 3 prime numbers.
Approach: To solve the problem mentioned above we have to find the count of prime numbers in the given array.
- Let the count of prime numbers is m.
- We can choose any K integers among m prime numbers.
- So the possible combination of choosing prime numbers in the subsequence is
and in the subsequence we can add any number of non – prime numbers because there is no restriction on the non prime numbers where count of non prime numbers will be (N – m). - We can choose any subset of the (N – m) for nonprime numbers in our subsequence.
- Possibility of choosing all subset of size (N – m) is pow(2, (m – N)).
- For generating subsequences, we will multiply prime number possibility with nonprime number possibility.
and in the subsequence we can add any number of non – prime numbers because there is no restriction on the non prime numbers where count of non prime numbers will be (N – m).
Sub sequence count = (Count of prime numbers) C (K) * pow(2, count of non-prime numbers)
Below is the implementation of the above approach:
C++
// C++ implementation to find// the count of subsequences// which consist exactly K primes#include <bits/stdc++.h>using namespace std;// Returns factorial of nint fact(int n){ int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res;}// Function to return total// number of combinationsint nCr(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function check whether a number// is prime or notbool isPrime(int n){ // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (int i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function for finding number of subsequences// which consists exactly K primesint countSubsequences(int arr[], int n, int k){ int countPrime = 0; for (int i = 0; i < n; i++) { if (isPrime(arr[i])) countPrime++; } // if number of primes are less than k if (countPrime < k) return 0; return nCr(countPrime, k) * pow(2, (n - countPrime));}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int K = 3; int n = sizeof(arr) / sizeof(arr[0]); cout << countSubsequences(arr, n, K); return 0;} |
Java
// Java implementation to find the// count of subsequences which // consist exactly K primesimport java.util.*;class GFG{ // Returns factorial of nstatic int fact(int n){ int res = 1; for(int i = 2; i <= n; i++) res = res * i; return res;}// Function to return total// number of combinationsstatic int nCr(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function check whether a number// is prime or notstatic boolean isPrime(int n){ // Corner case if (n <= 1) return false; // Check from 2 to n-1 for(int i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function for finding number of subsequences// which consists exactly K primesstatic int countSubsequences(int arr[], int n, int k){ int countPrime = 0; for(int i = 0; i < n; i++) { if (isPrime(arr[i])) countPrime++; } // If number of primes are less than k if (countPrime < k) return 0; return nCr(countPrime, k) * (int)Math.pow(2, (n - countPrime));}// Driver codepublic static void main(String args[]){ int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int K = 3; int n = arr.length; System.out.println(countSubsequences(arr, n, K));}}// This code is contributed by ANKITKUMAR34 |
Python3
# Python3 implementation to find the# count of subsequences which consist# exactly K primes# Returns factorial of ndef fact(n): res = 1; for i in range(2, n + 1): res = res * i return res# Function to return total# number of combinationsdef nCr(n, r): return (fact(n) // (fact(r) * fact(n - r)))# Function check whether a number# is prime or notdef isPrime(n): # Corner case if (n <= 1): return False; # Check from 2 to n-1 for i in range(2, n): if (n % i == 0): return False return True# Function for finding number of subsequences# which consists exactly K primesdef countSubsequences(arr, n, k): countPrime = 0 for i in range(n): if (isPrime(arr[i])): countPrime += 1 # If number of primes are less than k if (countPrime < k): return 0 return (nCr(countPrime, k) * pow(2, (n - countPrime)))# Driver codearr = [ 1, 2, 3, 4, 5, 6, 7 ]K = 3n = len(arr)print(countSubsequences(arr, n, K))# This code is contributed by ANKITKUMAR34 |
C#
// C# implementation to find the// count of subsequences which // consist exactly K primesusing System;class GFG{ // Returns factorial of nstatic int fact(int n){ int res = 1; for(int i = 2; i <= n; i++) res = res * i; return res;}// Function to return total// number of combinationsstatic int nCr(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function check whether a number// is prime or notstatic bool isPrime(int n){ // Corner case if (n <= 1) return false; // Check from 2 to n-1 for(int i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function for finding number of subsequences// which consists exactly K primesstatic int countSubsequences(int []arr, int n, int k){ int countPrime = 0; for(int i = 0; i < n; i++) { if (isPrime(arr[i])) countPrime++; } // If number of primes are less than k if (countPrime < k) return 0; return nCr(countPrime, k) * (int)Math.Pow(2, (n - countPrime));}// Driver codepublic static void Main(String []args){ int []arr = { 1, 2, 3, 4, 5, 6, 7 }; int K = 3; int n = arr.Length; Console.WriteLine(countSubsequences(arr, n, K));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript implementation to find// the count of subsequences// which consist exactly K primes// Returns factorial of nfunction fact(n){ var res = 1; for (var i = 2; i <= n; i++) res = res * i; return res;}// Function to return total// number of combinationsfunction nCr(n, r){ return fact(n) / (fact(r) * fact(n - r));}// Function check whether a number// is prime or notfunction isPrime(n){ // Corner case if (n <= 1) return false; // Check from 2 to n-1 for (var i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function for finding number of subsequences// which consists exactly K primesfunction countSubsequences(arr, n, k){ var countPrime = 0; for (var i = 0; i < n; i++) { if (isPrime(arr[i])) countPrime++; } // if number of primes are less than k if (countPrime < k) return 0; return nCr(countPrime, k) * Math.pow(2, (n - countPrime));}// Driver codevar arr = [ 1, 2, 3, 4, 5, 6, 7 ];var K = 3;var n = arr.length;document.write( countSubsequences(arr, n, K));</script> |
Output:
32
Time Complexity: O(N^2) .
Auxiliary Space: O(1) .
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!