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>
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>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)