Dada una array arr[] , la tarea es encontrar el número de subsecuencias no vacías de la array dada de modo que el producto de la subsecuencia sea un número compuesto .
Ejemplo:
Entrada: arr[] = {2, 3, 4}
Salida: 5
Explicación:
Hay 5 subsecuencias cuyo producto es número compuesto {4}, {2, 3}, {2, 4}, {3, 4}, { 2, 3, 4}.
Entrada: arr[] = {2, 1, 2}
Salida: 2
Explicación:
Hay 2 subsecuencias cuyo producto es número compuesto {2, 2}, {2, 1, 2}
Enfoque: el enfoque utilizado para encontrar el recuento de tales subsecuencias es similar al enfoque utilizado en este artículo . Además, el enfoque puede modificarse ligeramente para obtener el recuento de subsecuencias cuyo producto es un número primo.
Para resolver el problema mencionado anteriormente, tenemos que encontrar el número total de subsucesiones no vacías y restar la subsucesión cuyo producto no es un número compuesto . Los 3 casos posibles donde el producto no es un número compuesto son:
- Cualquier combinación no vacía de 1 que sea
pow(2, conteo de “1”) – 1
- Cualquier subsecuencia de longitud 1 que consta de un número primo que es básicamente el
conteo de numeros primos
- Combinación de 1 no vacío con un número primo que es
(pow(2, número de 1 ) – 1) * (recuento de números primos)
A continuación se muestra la implementación del enfoque anterior:
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 not
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 number
int 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 code
int 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 number
import java.util.*;
class GFG{
// Function to check whether a
// number is prime or not
static 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 number
static 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 code
public 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 not def 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 number def 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 code if __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 number
using System;
class GFG{
// Function to check whether a
// number is prime or not
static 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 number
static 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 code
public 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 not
function 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 number
function 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 code
var arr = [ 2, 1, 2 ];
var n = arr.length;
document.write( countSubsequences(arr, n));
</script>
Producción:
2