Dada una array vec[] de tamaño N de enteros no negativos. La tarea es contar el número de subsecuencias con la suma igual a S – 2 donde S es la suma de todos los elementos del arreglo .
Ejemplos:
Entrada: vec[] = {2, 0, 1, 2, 1}, N=5
Salida: 6
Explicación: {2, 0, 1, 1}, {2, 1, 1}, {2, 0, 2 }, {2, 2}, {0, 1, 2, 1}, {1, 2, 1}Entrada: vec[] = {2, 0, 2, 3, 1}, N=5
Salida: 4
Explicación: {2, 0, 3, 1}, {2, 3, 1}, {0, 2, 3 , 1}, {2, 3, 1}
Enfoque ingenuo: la idea es generar todas las subsecuencias y verificar que la suma de todas y cada una de las subsecuencias individuales sea igual a S-2 o no.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the total number
// of subsequences with sum S-2
void countTotal(vector<int>& vec)
{
// Calculating vector sum using
// accumulate function
int sum = accumulate(vec.begin(),
vec.end(), 0LL);
int N = (int)vec.size();
// Answer variable stores count
// of subsequences with desired sum
int answer = 0;
// Bitmasking technique to generate
// all possible subsequences
for (int mask = 0; mask < (1 << N); mask++) {
// Variable curr counts the
// sum of the current subsequence
int curr = 0;
for (int i = 0; i < N; i++) {
if ((mask & (1 << i)) != 0) {
// Include ith element
// of the vector
curr += vec[i];
}
}
if (curr == sum - 2)
answer++;
}
// Print the answer
cout << answer;
}
// Driver Code
int main()
{
// Initializing a vector
vector<int> vec = { 2, 0, 1, 2, 1 };
countTotal(vec);
return 0;
}
Java
// Java program for the above approach
public class GFG {
static int accumulate(int [] vec){
int sum1 = 0;
for (int i = 0; i < vec.length; i++)
sum1 += vec[i];
return sum1;
}
// Function to count the total number
// of subsequences with sum S-2
static void countTotal(int []vec)
{
// Calculating vector sum using
// accumulate function
int sum = accumulate(vec);
int N = vec.length;
// Answer variable stores count
// of subsequences with desired sum
int answer = 0;
// Bitmasking technique to generate
// all possible subsequences
for (int mask = 0; mask < (1 << N); mask++) {
// Variable curr counts the
// sum of the current subsequence
int curr = 0;
for (int i = 0; i < N; i++) {
if ((mask & (1 << i)) != 0) {
// Include ith element
// of the vector
curr += vec[i];
}
}
if (curr == sum - 2)
answer++;
}
// Print the answer
System.out.print(answer);
}
// Driver Code
public static void main (String[] args)
{
// Initializing a vector
int []vec = { 2, 0, 1, 2, 1 };
countTotal(vec);
}
}
// This code is contributed by AnkThon
Python3
# python3 program for the above approach # Function to count the total number # of subsequences with sum S-2 def countTotal(vec) : # Calculating vector sum using # accumulate function Sum = sum(vec) N = len(vec); # Answer variable stores count # of subsequences with desired sum answer = 0; # Bitmasking technique to generate # all possible subsequences for mask in range((1 << N)) : # Variable curr counts the # sum of the current subsequence curr = 0; for i in range(N) : if ((mask & (1 << i)) != 0) : # Include ith element # of the vector curr += vec[i]; if (curr == Sum - 2) : answer += 1; # Print the answer print(answer); # Driver Code if __name__ == "__main__" : # Initializing a vector vec = [ 2, 0, 1, 2, 1 ]; countTotal(vec); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
public class GFG {
static int accumulate(int[] vec)
{
int sum1 = 0;
for (int i = 0; i < vec.Length; i++)
sum1 += vec[i];
return sum1;
}
// Function to count the total number
// of subsequences with sum S-2
static void countTotal(int[] vec)
{
// Calculating vector sum using
// accumulate function
int sum = accumulate(vec);
int N = vec.Length;
// Answer variable stores count
// of subsequences with desired sum
int answer = 0;
// Bitmasking technique to generate
// all possible subsequences
for (int mask = 0; mask < (1 << N); mask++) {
// Variable curr counts the
// sum of the current subsequence
int curr = 0;
for (int i = 0; i < N; i++) {
if ((mask & (1 << i)) != 0) {
// Include ith element
// of the vector
curr += vec[i];
}
}
if (curr == sum - 2)
answer++;
}
// Print the answer
Console.WriteLine(answer);
}
// Driver Code
public static void Main(string[] args)
{
// Initializing a vector
int[] vec = { 2, 0, 1, 2, 1 };
countTotal(vec);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to count the total number
// of subsequences with sum S-2
function countTotal(vec) {
// Calculating vector sum using
// accumulate function
let sum = vec.reduce((acc, curr) => acc + curr, 0)
let N = vec.length;
// Answer variable stores count
// of subsequences with desired sum
let answer = 0;
// Bitmasking technique to generate
// all possible subsequences
for (let mask = 0; mask < (1 << N); mask++) {
// Variable curr counts the
// sum of the current subsequence
let curr = 0;
for (let i = 0; i < N; i++) {
if ((mask & (1 << i)) != 0) {
// Include ith element
// of the vector
curr += vec[i];
}
}
if (curr == sum - 2)
answer++;
}
// Print the answer
document.write(answer);
}
// Driver Code
// Initializing a vector
let vec = [2, 0, 1, 2, 1];
countTotal(vec);
// This code is contributed by saurabh_jaiswal.
</script>
Producción
6
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque Eficiente: La idea es usar la Combinatoria que, además de los 0, 1 y 2 , todos los demás elementos en nuestra array serán parte de las subsecuencias deseadas. Llamémoslos elementos extra. Luego, cuente las ocurrencias de 0, 1 y 2 en la array. Digamos que la cuenta de 0 es x , la cuenta de 1 es y , la cuenta de 2 es z .
- Contemos el número de subsecuencias deseadas si todos los 2 y los elementos adicionales están en la subsecuencia. Ahora puede haber exactamente y – 2 elementos de y. Tenga en cuenta que no hay restricción para tomar 0, ya que no contribuye en nada a nuestra suma de subsecuencias.
- Por lo tanto, la cuenta total de tales subsecuencias = cuenta1 = 2 x × y C y – 2 = 2 x × y C 2 (Ya que, n C 0 + n C 1 + . . . + n C n = 2 n ).
- Contemos el número de subsecuencias si todos los 1 están en nuestra subsecuencia. Ahora puede haber exactamente z – 1 elementos de z.
- Por lo tanto, la cuenta total de tales subsecuencias = cuenta2 = 2 x × z C z – 1 = 2 x × z C 1
- Cuenta total de subsecuencias cuya suma es igual a S – 2, cuenta = cuenta1 + cuenta2 = 2 x × ( y C 2 + z C 1 )
Siga los pasos a continuación para resolver el problema:
- Inicializa la variable sum como la suma de la array.
- Inicialice la respuesta variable como 0 para almacenar la respuesta.
- Inicialice las variables countOfZero, countOfOne y countOfTwo para almacenar el recuento de 0, 1 y 2.
- Recorra la array vec[] usando el iterador x y realice las siguientes tareas:
- Cuente las ocurrencias de 0, 1 y 2.
- Inicialice las variables value1 como 2 countOfZero .
- Inicialice la variable value2 como (countOfOne * (countOfOne – 1)) / 2 .
- Inicialice la variable value3 como countOfTwo.
- Establezca el valor de la respuesta como valor1 * (valor2 + valor).
- Después de realizar los pasos anteriores, imprima el valor de la respuesta como la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the total number
// of subsequences with sum S-2
void countTotal(vector<int>& vec)
{
// Calculating vector sum using
// accumulate function
int sum = accumulate(vec.begin(),
vec.end(), 0LL);
int N = (int)vec.size();
// Answer variable stores count
// of subsequences with desired sum
int answer = 0;
int countOfZero = 0,
countOfOne = 0,
countOfTwo = 0;
for (auto x : vec) {
if (x == 0)
countOfZero++;
else if (x == 1)
countOfOne++;
else if (x == 2)
countOfTwo++;
}
// Select any number of
// zeroes from 0 to count[0]
// which is equivalent
// to 2 ^ countOfZero
int value1 = pow(2, countOfZero);
// Considering all 2's
// and extra elements
int value2
= (countOfOne
* (countOfOne - 1))
/ 2;
// Considering all 1's
// and extra elements
int value3 = countOfTwo;
// Calculating final answer
answer = value1 * (value2 + value3);
// Print the answer
cout << answer;
}
// Driver Code
int main()
{
// Initializing a vector
vector<int> vec = { 2, 0, 1, 2, 1 };
countTotal(vec);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Function to count the total number
// of subsequences with sum S-2
static void countTotal(int[] arr)
{
int N = arr.length;
// Answer variable stores count
// of subsequences with desired sum
int answer = 0;
int countOfZero = 0, countOfOne = 0, countOfTwo = 0;
for (int i = 0; i < N; i++) {
if (arr[i] == 0)
countOfZero++;
else if (arr[i] == 1)
countOfOne++;
else if (arr[i] == 2)
countOfTwo++;
}
// Select any number of
// zeroes from 0 to count[0]
// which is equivalent
// to 2 ^ countOfZero
int value1 = (1 << countOfZero);
// Considering all 2's
// and extra elements
int value2 = (countOfOne * (countOfOne - 1)) / 2;
// Considering all 1's
// and extra elements
int value3 = countOfTwo;
// Calculating final answer
answer = value1 * (value2 + value3);
// Print the answer
System.out.println(answer);
}
// Driver Code
public static void main(String[] args)
{
// Initializing an array
int[] arr = { 2, 0, 1, 2, 1 };
countTotal(arr);
}
}
// This code is contributed by maddler.
Python3
# Python3 program for the above approach # Function to count the total number # of subsequences with sum S-2 def countTotal(vec) : # Calculating vector sum using # accumulate function sum1 = sum(vec); N = len(vec); # Answer variable stores count # of subsequences with desired sum answer = 0; countOfZero = 0; countOfOne = 0; countOfTwo = 0; for x in vec : if (x == 0) : countOfZero += 1; elif (x == 1) : countOfOne += 1; elif (x == 2) : countOfTwo += 1; # Select any number of # zeroes from 0 to count[0] # which is equivalent # to 2 ^ countOfZero value1 = 2 ** countOfZero; # Considering all 2's # and extra elements value2 = (countOfOne * (countOfOne - 1)) // 2; # Considering all 1's # and extra elements value3 = countOfTwo; # Calculating final answer answer = value1 * (value2 + value3); # Print the answer print(answer); # Driver Code if __name__ == "__main__" : # Initializing a vector vec = [ 2, 0, 1, 2, 1 ]; countTotal(vec); # This code is contributed by AnkThon
C#
// Above approach implemented in C#
using System;
public class GFG {
// Function to count the total number
// of subsequences with sum S-2
static void countTotal(int[] arr)
{
int N = arr.Length;
// Answer variable stores count
// of subsequences with desired sum
int answer = 0;
int countOfZero = 0, countOfOne = 0, countOfTwo = 0;
for (int i = 0; i < N; i++) {
if (arr[i] == 0)
countOfZero++;
else if (arr[i] == 1)
countOfOne++;
else if (arr[i] == 2)
countOfTwo++;
}
// Select any number of
// zeroes from 0 to count[0]
// which is equivalent
// to 2 ^ countOfZero
int value1 = (1 << countOfZero);
// Considering all 2's
// and extra elements
int value2 = (countOfOne * (countOfOne - 1)) / 2;
// Considering all 1's
// and extra elements
int value3 = countOfTwo;
// Calculating final answer
answer = value1 * (value2 + value3);
// Print the answer
Console.WriteLine(answer);
}
// Driver Code
public static void Main(string[] args)
{
// Initializing an array
int[] arr = { 2, 0, 1, 2, 1 };
countTotal(arr);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to count the total number
// of subsequences with sum S-2
function countTotal(vec)
{
// Calculating vector sum using
// accumulate function
let sum = vec.reduce(function (accumulator, currentValue) {
return accumulator + currentValue;
}, 0);
let N = vec.length;
// Answer variable stores count
// of subsequences with desired sum
let answer = 0;
let countOfZero = 0,
countOfOne = 0,
countOfTwo = 0;
for (let x of vec) {
if (x == 0)
countOfZero++;
else if (x == 1)
countOfOne++;
else if (x == 2)
countOfTwo++;
}
// Select any number of
// zeroes from 0 to count[0]
// which is equivalent
// to 2 ^ countOfZero
let value1 = Math.pow(2, countOfZero);
// Considering all 2's
// and extra elements
let value2
= (countOfOne
* (countOfOne - 1))
/ 2;
// Considering all 1's
// and extra elements
let value3 = countOfTwo;
// Calculating final answer
answer = value1 * (value2 + value3);
// Print the answer
document.write(answer);
}
// Driver Code
// Initializing a vector
let vec = [2, 0, 1, 2, 1];
countTotal(vec);
// This code is contributed by Potta Lokesh
</script>
Producción
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)