Número de subsecuencias con suma par e impar | conjunto 2

Dada una array arr[] de tamaño N . La tarea es encontrar el número de subsecuencias cuya suma es par y el número de subsecuencias cuya suma es impar.
Ejemplos: 
 

Entrada: arr[] = {1, 2, 2, 3} 
Salida: EvenSum = 7, OddSum = 8 
Hay 2 ^N -1 subsecuencias posibles. 
Las subsucesiones con suma par son 
1) {1, 3} Suma = 4 
2) {1, 2, 2, 3} Suma = 8 
3) {1, 2, 3} Suma = 6 (De índice 1) 
4) { 1, 2, 3} Suma = 6 (De índice 2) 
5) {2} Suma = 2 (De índice 1) 
6) {2, 2} Suma = 4 
7) {2} Suma = 2 (De índice 2) 
y el resto de la subsecuencia es de suma impar.
Entrada: arr[] = { 2, 2, 2, 2 } 
Salida: EvenSum = 15, OddSum = 0 
 

Enfoque: este artículo ya existe aquí y tiene una complejidad de tiempo  donde N es el tamaño de la array. Visite aquí antes de continuar.
 

• Si podemos encontrar el número de subsecuencias impares, entonces podemos encontrar fácilmente el número de subsecuencias pares.
• Las subsecuencias impares se pueden formar de dos maneras: 
  1. Tomando números impares veces impares.
  2. Tomando número par e impar tiempo impar.
• A continuación se muestran algunas variables y su definición: 
  • N = Número total de elementos en la array.
  • Par = Número total de pares en la array.
  • Impar = Número total de impares en la array.
  • Tseq = Número total de subsecuencias.
  • Oseq = Número total de subsecuencias con solo número impar.
  • Eseq = Número total de subsecuencias con número par.
  • OddSumSeq = Número total de subsecuencias con suma impar.
  • EvenSumSeq = Número total de subsecuencias con suma par.

Tseq = 2 ^N – 1 = Subsecuencia Par + Subsecuencia Impar
Eseq = 2 ^Par
Oseq = C ₁ ^Impar + C ₃ ^Impar + C ₅ ^Impar + . . . . 
donde ^Impar C ₁ = Elegir 1 Impar 
^Impar C ₃ = Elegir 3 Impar y así sucesivamente
Podemos reducir la ecuación anterior por esta identidad, Por lo tanto,
Oseq = 2 ^{Impar – 1}
Entonces, por lo tanto, para la subsecuencia de suma impar total, se puede calcular mediante multiplicando estos resultados anteriores
OddSumSeq = 2 ^Even* 2 ^{Impar – 1}
EvenSumSeq = 2 ^N – 1 – OddSumSeq
 

A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find number of
// Subsequences with Even and Odd Sum
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of
// Subsequences with Even and Odd Sum
pair<int, int> countSum(int arr[], int n)
{
    int NumberOfOdds = 0, NumberOfEvens = 0;
 
    // Counting number of odds
    for (int i = 0; i < n; i++)
        if (arr[i] & 1)
            NumberOfOdds++;
 
    // Even count
    NumberOfEvens = n - NumberOfOdds;
 
    int NumberOfOddSubsequences = (1 << NumberOfEvens)
                                  * (1 << (NumberOfOdds - 1));
 
    // Total Subsequences is (2^n - 1)
    // For NumberOfEvenSubsequences subtract
    // NumberOfOddSubsequences from total
    int NumberOfEvenSubsequences = (1 << n) - 1
                                   - NumberOfOddSubsequences;
 
    return { NumberOfEvenSubsequences,
             NumberOfOddSubsequences };
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Calling the function
    pair<int, int> ans = countSum(arr, n);
 
    cout << "EvenSum = " << ans.first;
    cout << " OddSum = " << ans.second;
 
    return 0;
}

// Java program to find number of
// Subsequences with Even and Odd Sum
import java.util.*;
 
class GFG
{
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to find number of
// Subsequences with Even and Odd Sum
static pair countSum(int arr[], int n)
{
    int NumberOfOdds = 0, NumberOfEvens = 0;
 
    // Counting number of odds
    for (int i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            NumberOfOdds++;
 
    // Even count
    NumberOfEvens = n - NumberOfOdds;
 
    int NumberOfOddSubsequences = (1 << NumberOfEvens) *
                                  (1 << (NumberOfOdds - 1));
 
    // Total Subsequences is (2^n - 1)
    // For NumberOfEvenSubsequences subtract
    // NumberOfOddSubsequences from total
    int NumberOfEvenSubsequences = (1 << n) - 1 -
                                    NumberOfOddSubsequences;
 
    return new pair(NumberOfEvenSubsequences,
                    NumberOfOddSubsequences);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 2, 3 };
 
    int n = arr.length;
 
    // Calling the function
    pair ans = countSum(arr, n);
 
    System.out.print("EvenSum = " + ans.first);
    System.out.print(" OddSum = " + ans.second);
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program to find number of
# Subsequences with Even and Odd Sum
 
# Function to find number of
# Subsequences with Even and Odd Sum
def countSum(arr, n) :
 
    NumberOfOdds = 0; NumberOfEvens = 0;
 
    # Counting number of odds
    for i in range(n) :
        if (arr[i] & 1) :
            NumberOfOdds += 1;
 
    # Even count
    NumberOfEvens = n - NumberOfOdds;
 
    NumberOfOddSubsequences = (1 << NumberOfEvens) * \
                              (1 << (NumberOfOdds - 1));
 
    # Total Subsequences is (2^n - 1)
    # For NumberOfEvenSubsequences subtract
    # NumberOfOddSubsequences from total
    NumberOfEvenSubsequences = (1 << n) - 1 - \
                                NumberOfOddSubsequences;
 
    return (NumberOfEvenSubsequences,
            NumberOfOddSubsequences);
 
# Driver code
if __name__ == "__main__":
 
    arr = [ 1, 2, 2, 3 ];
 
    n = len(arr);
 
    # Calling the function
    ans = countSum(arr, n);
 
    print("EvenSum =", ans[0], end = " ");
    print("OddSum =", ans[1]);
 
# This code is contributed by AnkitRai01

// C# program to find number of
// Subsequences with Even and Odd Sum
using System;
     
class GFG
{
public class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to find number of
// Subsequences with Even and Odd Sum
static pair countSum(int []arr, int n)
{
    int NumberOfOdds = 0, NumberOfEvens = 0;
 
    // Counting number of odds
    for (int i = 0; i < n; i++)
        if (arr[i] % 2 == 1)
            NumberOfOdds++;
 
    // Even count
    NumberOfEvens = n - NumberOfOdds;
 
    int NumberOfOddSubsequences = (1 << NumberOfEvens) *
                                  (1 << (NumberOfOdds - 1));
 
    // Total Subsequences is (2^n - 1)
    // For NumberOfEvenSubsequences subtract
    // NumberOfOddSubsequences from total
    int NumberOfEvenSubsequences = (1 << n) - 1 -
                                    NumberOfOddSubsequences;
 
    return new pair(NumberOfEvenSubsequences,
                    NumberOfOddSubsequences);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 2, 3 };
 
    int n = arr.Length;
 
    // Calling the function
    pair ans = countSum(arr, n);
 
    Console.Write("EvenSum = " + ans.first);
    Console.Write(" OddSum = " + ans.second);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to find number of
// Subsequences with Even and Odd Sum
 
// Function to find number of
// Subsequences with Even and Odd Sum
function countSum(arr, n) {
    let NumberOfOdds = 0, NumberOfEvens = 0;
 
    // Counting number of odds
    for (let i = 0; i < n; i++)
        if (arr[i] & 1)
            NumberOfOdds++;
 
    // Even count
    NumberOfEvens = n - NumberOfOdds;
 
    let NumberOfOddSubsequences = (1 << NumberOfEvens)
        * (1 << (NumberOfOdds - 1));
 
    // Total Subsequences is (2^n - 1)
    // For NumberOfEvenSubsequences subtract
    // NumberOfOddSubsequences from total
    let NumberOfEvenSubsequences = (1 << n) - 1
        - NumberOfOddSubsequences;
 
    return [NumberOfEvenSubsequences,
        NumberOfOddSubsequences];
}
 
// Driver code
let arr = [1, 2, 2, 3];
 
let n = arr.length;
 
// Calling the function
let ans = countSum(arr, n);
 
document.write("EvenSum = " + ans[0]);
document.write(" OddSum = " + ans[1]);
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

EvenSum = 7 OddSum = 8

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)