Dados N enteros positivos A 1 , A 2 , …, 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 parEntrada: 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 1 + A 2 + A 3 ) + ((A 1 * A 2 ) + (A 2 * A 3 ) + (A 3 * A 1 ) + (A 1 * A 2 * A 3 )
- Ahora, la misma expresión se reestructura de la siguiente manera:
(1 + A 1 ) + (A 2 + A 1 * A 2 ) + (A 3 + A 3 * A 1 ) + (A 2 * A 3 + A 1 * A 2 * A 3 )
=> (1 + A 1 ) + A 2 * (1 + A 1 ) + A 3 * (1 + A 1 ) + A 2 * A 3 * (1 + A 1 )
- Tomando (1 + A 1 ) común de la ecuación anterior,
(1 + A 1 ) * (1 + A 2 + A 2 + (A 2 * A 3 ))
=> (1 + A 1 ) * (1 + A 2 + A 3 * (1 + A 2 )
- Finalmente, al tomar (1 + A 2 ) común, la expresión final se convierte en:
(1 + A 1 ) * (1 + A 2 ) * (1 + A 3 )
- Por simetría, para N elementos, la expresión S se convierte en:
(1 + A 1 ) * (1 + A 2 ) * (1 + A 3 ) … * (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++
// 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
// 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
# 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#
// 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
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA