Given an array arr[], the task is to find the number of non-empty subsequences from the given array such that the product of subsequence is a composite number.
Example:
Input: arr[] = {2, 3, 4}
Output: 5
Explanation:
There are 5 subsequences whose product is composite number {4}, {2, 3}, {2, 4}, {3, 4}, {2, 3, 4}.
Input: arr[] = {2, 1, 2}
Output: 2
Explanation:
There is 2 subsequences whose product is composite number {2, 2}, {2, 1, 2}
Approach: The approach used to find the count of such subsequences is similar to the approach used in this article. Also, the approach can slightly tweaked to get the count of subsequences whose product is a Prime number.
To solve the problem mentioned above, we have to find the total number of non-empty subsequences and subtract the subsequence whose product is not a composite number. The 3 possible cases where the product is not a composite number are:
- Any nonempty combination of 1 that is
pow(2, count of “1”) – 1
- Any subsequence of length 1 which consists of a prime number that is basically the
count of prime numbers
- Combination of non-empty 1 with a prime number that is
(pow(2, number of 1 ) – 1) * (count of prime numbers)
Below is the implementation of above approach:
C++
// C++ implementation to count all// subsequence whose product// is Composite number#include <bits/stdc++.h>using namespace std;// Function to check whether a// number is prime or notbool isPrime(int n){ if (n <= 1) return false; for (int i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function to find number of subsequences// whose product is a composite numberint countSubsequences(int arr[], int n){ // Find total non empty subsequence int totalSubsequence = pow(2, n) - 1; int countPrime = 0, countOnes = 0; // Find count of prime number and ones for (int i = 0; i < n; i++) { if (arr[i] == 1) countOnes++; else if (isPrime(arr[i])) countPrime++; } int compositeSubsequence; // Calculate the non empty one subsequence int onesSequence = pow(2, countOnes) - 1; // Find count of composite subsequence compositeSubsequence = totalSubsequence - countPrime - onesSequence - onesSequence * countPrime; return compositeSubsequence;}// Driver codeint main(){ int arr[] = { 2, 1, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countSubsequences(arr, n); return 0;} |
Java
// Java implementation to count all// subsequence whose product// is Composite numberimport java.util.*;class GFG{// Function to check whether a// number is prime or notstatic boolean isPrime(int n){ if (n <= 1) return false; for (int i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function to find number of subsequences// whose product is a composite numberstatic int countSubsequences(int arr[], int n){ // Find total non empty subsequence int totalSubsequence = (int)(Math.pow(2, n) - 1); int countPrime = 0, countOnes = 0; // Find count of prime number and ones for (int i = 0; i < n; i++) { if (arr[i] == 1) countOnes++; else if (isPrime(arr[i])) countPrime++; } int compositeSubsequence; // Calculate the non empty one subsequence int onesSequence = (int)(Math.pow(2, countOnes) - 1); // Find count of composite subsequence compositeSubsequence = totalSubsequence - countPrime - onesSequence - onesSequence * countPrime; return compositeSubsequence;}// Driver codepublic static void main(String[] args){ int arr[] = { 2, 1, 2 }; int n = arr.length; System.out.print(countSubsequences(arr, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to count # all subsequence whose product# is composite number# Function to check whether # a number is prime or notdef isPrime(n): if (n <= 1): return False; for i in range(2, n): if (n % i == 0): return False; return True;# Function to find number of subsequences# whose product is a composite numberdef countSubsequences(arr, n): # Find total non empty subsequence totalSubsequence = (int)(pow(2, n) - 1); countPrime = 0; countOnes = 0; # Find count of prime number and ones for i in range(n): if (arr[i] == 1): countOnes += 1; elif (isPrime(arr[i])): countPrime += 1; compositeSubsequence = 0; # Calculate the non empty one subsequence onesSequence = (int)(pow(2, countOnes) - 1); # Find count of composite subsequence compositeSubsequence = (totalSubsequence - countPrime - onesSequence - onesSequence * countPrime); return compositeSubsequence;# Driver codeif __name__ == '__main__': arr = [ 2, 1, 2 ]; n = len(arr); print(countSubsequences(arr, n));# This code is contributed by 29AjayKumar |
C#
// C# implementation to count all// subsequence whose product// is Composite numberusing System;class GFG{// Function to check whether a// number is prime or notstatic bool isPrime(int n){ if (n <= 1) return false; for (int i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function to find number of subsequences// whose product is a composite numberstatic int countSubsequences(int []arr, int n){ // Find total non empty subsequence int totalSubsequence = (int)(Math.Pow(2, n) - 1); int countPrime = 0, countOnes = 0; // Find count of prime number and ones for (int i = 0; i < n; i++) { if (arr[i] == 1) countOnes++; else if (isPrime(arr[i])) countPrime++; } int compositeSubsequence; // Calculate the non empty one subsequence int onesSequence = (int)(Math.Pow(2, countOnes) - 1); // Find count of composite subsequence compositeSubsequence = totalSubsequence - countPrime - onesSequence - onesSequence * countPrime; return compositeSubsequence;}// Driver codepublic static void Main(){ int []arr = { 2, 1, 2 }; int n = arr.Length; Console.Write(countSubsequences(arr, n));}}// This code is contributed by Nidhi_biet |
Javascript
<script>// Javascript implementation to count all// subsequence whose product// is Composite number// Function to check whether a// number is prime or notfunction isPrime(n){ if (n <= 1) return false; for (var i = 2; i < n; i++) if (n % i == 0) return false; return true;}// Function to find number of subsequences// whose product is a composite numberfunction countSubsequences( arr, n){ // Find total non empty subsequence var totalSubsequence = Math.pow(2, n) - 1; var countPrime = 0, countOnes = 0; // Find count of prime number and ones for (var i = 0; i < n; i++) { if (arr[i] == 1) countOnes++; else if (isPrime(arr[i])) countPrime++; } var compositeSubsequence; // Calculate the non empty one subsequence var onesSequence = Math.pow(2, countOnes) - 1; // Find count of composite subsequence compositeSubsequence = totalSubsequence - countPrime - onesSequence - onesSequence * countPrime; return compositeSubsequence;}// Driver codevar arr = [ 2, 1, 2 ];var n = arr.length;document.write( countSubsequences(arr, n));</script> |
Output:
2
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!
