Count of subsequences of length atmost K containing distinct prime elements | C ++ Program to find the count of distinct prime subsequences at most of of length K from a given array ; Initialize all indices as true ; A value in prime [ i ] will finally be false if i is not a prime , else true ; If prime [ p ] is true , then it is a prime ; Update all multiples of p as false , i . e . non - prime ; Returns number of subsequences of maximum length k and contains distinct primes ; Store the primes in the given array ; Sort the primes ; Store the frequencies of all the distinct primes ; Store the frequency of primes ; Store the sum of all frequencies ; Store the length of subsequence at every instant ; Store the frequency ; Store the previous count of updated DP ; Calculate total subsequences of current of_length ; Add the number of subsequences to the answer ; Update the value in dp [ i ] ; Store the updated dp [ i ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool prime [ 100001 ] ; void SieveOfEratosthenes ( ) { memset ( prime , true , sizeof ( prime ) ) ; prime [ 0 ] = prime [ 1 ] = false ; for ( int p = 2 ; p * p <= 100000 ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= 100000 ; i += p ) prime [ i ] = false ; } } } int distinctPrimeSubSeq ( int a [ ] , int n , int k ) { SieveOfEratosthenes ( ) ; vector < int > primes ; for ( int i = 0 ; i < n ; i ++ ) { if ( prime [ a [ i ] ] ) primes . push_back ( a [ i ] ) ; } int l = primes . size ( ) ; sort ( primes . begin ( ) , primes . end ( ) ) ; vector < int > b ; vector < int > dp ; int sum = 0 ; for ( int i = 0 ; i < l ; ) { int count = 1 , x = a [ i ] ; i ++ ; while ( i < l && a [ i ] == x ) { count ++ ; i ++ ; } b . push_back ( count ) ; dp . push_back ( count ) ; sum += count ; } int of_length = 2 ; int len = dp . size ( ) ; int ans = 0 ; while ( of_length <= k ) { int freq = 0 ; int prev = 0 ; for ( int i = 0 ; i < ( len - 1 ) ; i ++ ) { freq += dp [ i ] ; int j = sum - freq ; int subseq = b [ i ] * j ; ans += subseq ; dp [ i ] = subseq ; prev += dp [ i ] ; } len -- ; sum = prev ; of_length ++ ; } ans += ( l + 1 ) ; return ans ; } int main ( ) { int a [ ] = { 1 , 2 , 2 , 3 , 3 , 4 , 5 } ; int n = sizeof ( a ) / sizeof ( int ) ; int k = 3 ; cout << distinctPrimeSubSeq ( a , n , k ) ; return 0 ; }