Paridad de la expresión matemática dada usando N números dados

Dados N enteros positivos A ₁ , A ₂ , …, _AN , la tarea es determinar la paridad de la expresión S. 
Para los N números dados, la expresión S se da como: 

 

Ejemplos: 

Entrada: N = 3, A1 = 2, A2 = 3, A3 = 1 
Salida: Par 
Explicación: 
S = 1 + (2 + 3 + 1) + (2*3 + 3*1 + 1*2) + (2 *3*1) = 24, que es par

Entrada: N = 2, A1 = 2, A2 = 4 
Salida: Impar 
Explicación: 
S = 1 + (2 + 4) + (2 * 4) = 15, que es impar 

Enfoque ingenuo: El enfoque ingenuo para este problema es reemplazar todos los valores de A _i en la expresión dada y encontrar la paridad de la expresión dada. Este método no funciona para valores más altos de N ya que la multiplicación no es una operación constante para números de orden superior. Y también, el valor podría volverse tan grande que podría causar un desbordamiento de enteros. 

Enfoque eficiente: la idea es realizar algún procesamiento en la expresión y reducirla a términos más simples para que la paridad pueda verificarse sin calcular el valor. Sea N = 3. Entonces:
 

• La expresión S es: 

1 + (A ₁ + A ₂ + A ₃ ) + ((A ₁ * A ₂ ) + (A ₂ * A ₃ ) + (A ₃ * A ₁ ) + (A ₁ * A ₂ * A ₃ )  

• Ahora, la misma expresión se reestructura de la siguiente manera: 

(1 + A ₁ ) + (A ₂ + A ₁ * A ₂ ) + (A ₃ + A ₃ * A ₁ ) + (A ₂ * A ₃ + A ₁ * A ₂ * A ₃ )
=> (1 + A ₁ ) + A ₂ * (1 + A ₁ ) + A ₃ * (1 + A ₁ ) + A ₂ * A ₃ * (1 + A ₁ ) 

• Tomando (1 + A ₁ ) común de la ecuación anterior, 

(1 + A ₁ ) * (1 + A ₂ + A ₂ + (A ₂ * A ₃ ))
=> (1 + A ₁ ) * (1 + A ₂ + A ₃ * (1 + A ₂ ) 

• Finalmente, al tomar (1 + A ₂ ) común, la expresión final se convierte en: 

(1 + A ₁ ) * (1 + A ₂ ) * (1 + A ₃ ) 

• Por simetría, para N elementos, la expresión S se convierte en: 

(1 + A ₁ ) * (1 + A ₂ ) * (1 + A ₃ ) … * (1 + A _N ) 

• Claramente, para que un número se convierta en paridad par, la respuesta debe ser par. Se sabe que la respuesta es par si alguno de los números es par.
• Por lo tanto, la idea es verificar si alguno de los números en la entrada dada es impar. Si es así, al sumar uno, se vuelve par y el valor es paridad par.

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

// C++ program to determine the
// parity of the given mathematical
// expression
 
#include <bits/stdc++.h>
using namespace std;
 
void getParity(
    int n,
    const vector<int>& A)
{
 
    // Iterating through the
    // given integers
    for (auto x : A) {
        if (x & 1) {
 
            // If any odd number
            // is present, then S
            // is even parity
            cout << "Even" << endl;
            return;
        }
    }
 
    // Else, S is odd parity
    cout << "Odd" << endl;
}
 
// Driver code
int main()
{
 
    int N = 3;
    vector<int> A = { 2, 3, 1 };
    getParity(N, A);
 
    return 0;
}

// Java program to determine the
// parity of the given mathematical
// expression
class GFG{
 
static void getParity(int n, int []A)
{
 
    // Iterating through the
    // given integers
    for (int x : A)
    {
        if ((x & 1) == 1)
        {
 
            // If any odd number
            // is present, then S
            // is even parity
            System.out.println("Even");
            return;
        }
    }
 
    // Else, S is odd parity
    System.out.println("Odd");
}
 
// Driver code
public static void main(String[] args)
{
    int N = 3;
    int [] A = { 2, 3, 1 };
    getParity(N, A);
}
}
 
// This code is contributed by AnkitRai01

# Python3 program to determine the
# parity of the given mathematical
# expression
def getParity(n, A):
 
    # Iterating through
    # the given integers
    for x in A:
        if (x & 1):
 
            # If any odd number
            # is present, then S
            # is even parity
            print("Even")
            return
 
    # Else, S is odd parity
    print("Odd")
     
# Driver code
if __name__ == '__main__':
 
    N = 3
    A = [ 2, 3, 1 ]
     
    getParity(N, A)
 
# This code is contributed by mohit kumar 29

// C# program to determine the
// parity of the given mathematical
// expression
using System;
 
public class GFG{
 
    static void getParity(int n, int []A)
    {
     
        // Iterating through the
        // given integers
        foreach (int x in A)
        {
            if ((x & 1) == 1)
            {
     
                // If any odd number
                // is present, then S
                // is even parity
                Console.WriteLine("Even");
                return;
            }
        }
     
        // Else, S is odd parity
        Console.WriteLine("Odd");
    }
     
    // Driver code
    public static void Main(string[] args)
    {
        int N = 3;
        int [] A = { 2, 3, 1 };
        getParity(N, A);
    }
}
 
// This code is contributed by AnkitRai01

<script>
// Javascript program to determine the
// parity of the given mathematical
// expression
 
function getParity(n, A)
{
   
    // Iterating through the
    // given integers
    for (let x in A)
    {
        if ((x & 1) == 1)
        {
   
            // If any odd number
            // is present, then S
            // is even parity
            document.write("Even");
            return;
        }
    }
   
    // Else, S is odd parity
    document.write("Odd");
}
 
  // Driver Code
     
     let N = 3;
    let A = [ 2, 3, 1 ];
    getParity(N, A);
       
</script>

Even

Complejidad temporal: O(N) , donde N es el número de números dados.