Dados dos arreglos arr1[] y arr2[] de tamaño N , la tarea es contar el número mínimo de intercambios de elementos del mismo índice de los arreglos arr1[] y arr2[] necesarios para hacer la suma de todos los elementos de ambos las arrays incluso. Si no es posible, imprima “-1” .
Ejemplos:
Entrada: arr1[] = {1, 4, 2, 3}, arr2[] = {2, 3, 4, 1}
Salida: 0
Explicación: La suma de todos los elementos de arr1[] y arr2[] es 10 y 10 respectivamente, que ya es par. Por lo tanto, el conteo de operaciones requeridas es 0.Entrada: arr1[] = {11, 14, 20, 2}, arr2[] = {5, 9, 6, 3}
Salida: 1
Explicación: La suma de todos los elementos de arr1[] y arr2[] es 37 y 23 respectivamente. Intercambiando arr1[1]( = 14) y arr2[1]( = 9) hace la suma de arr1[] y arr2[], 32 y 28 respectivamente. Por lo tanto, el conteo de operaciones requeridas es 1.
Enfoque: La idea se basa en las siguientes observaciones, suponiendo que la suma de la array arr1[] es sumArr1 y la de arr2[] es sumArr2 .
- Si sumArr1 es par y sumArr2 es par: No se requieren intercambios.
- Si sumArr1 es impar y sumArr2 es impar: busque un par de elementos del mismo índice cuya suma sea impar e intercámbielos. Tal par contiene un número par y un número impar. Intercambiarlos aumenta la suma de una array en 1 y disminuye la de la otra array en 1 . Por lo tanto, la suma de ambas arrays es par.
- Si sumArr1 es par y sumArr2 es impar: No es posible hacer que la suma de ambas arrays sea par.
- Si sumArr1 es impar y sumArr2 es par: No es posible hacer que la suma de ambas arrays sea par.
Siga los pasos a continuación para resolver el problema:
- Inicialice sumArr1 = 0 y sumArr2 = 0 para almacenar la suma de arr1[] y arr2[] respectivamente.
- Si se encuentra que sumArr1 y sumArr2 son pares, imprima 0 .
- Si se encuentra que sumArr1 y sumArr2 son impares, itere un bucle sobre el rango [0, N – 1] y verifique si existe algún par correspondiente cuya suma sea impar o no. Si se encuentra alguno de esos pares, imprima 1 .
- De lo contrario, para todos los demás casos, imprima -1 .
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 minimum swaps // of same-indexed elements from arrays // arr1[] and arr2[] required to make // the sum of both the arrays even void minimumSwaps(int arr1[], int arr2[], int n) { // Store the sum of elements of // the array arr1 and arr2 respectively int sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for (int i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { cout << 0; return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not int flag = -1; // Traverse the array for (int i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1){ flag = 1; break; } } // Print the answer and return cout << flag; return; } // For all other cases, print -1 cout << -1; } // Driver Code int main() { int arr1[] = { 11, 14, 20, 2 }; int arr2[] = { 5, 9, 6, 3 }; int N = sizeof(arr1) / sizeof(arr1[0]); // Function Call minimumSwaps(arr1, arr2, N); return 0; }
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to count the minimum swaps // of same-indexed elements from arrays // arr1[] and arr2[] required to make // the sum of both the arrays even static void minimumSwaps(int arr1[], int arr2[], int n) { // Store the sum of elements of // the array arr1 and arr2 respectively int sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for(int i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { System.out.print(0); return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not int flag = -1; // Traverse the array for(int i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1) { flag = 1; break; } } // Print the answer and return System.out.print(flag); return; } // For all other cases, print -1 System.out.print(-1); } // Driver code public static void main(String[] args) { int arr1[] = { 11, 14, 20, 2 }; int arr2[] = { 5, 9, 6, 3 }; int N = arr1.length; // Function Call minimumSwaps(arr1, arr2, N); } } // This code is contributed by jithin
Python3
# Python program for the above approach # Function to count the minimum swaps # of same-indexed elements from arrays # arr1 and arr2 required to make # the sum of both the arrays even def minimumSwaps(arr1, arr2, n): # Store the sum of elements of # the array arr1 and arr2 respectively sumArr1 = 0; sumArr2 = 0; # Store the array sum of both the arrays for i in range(n): sumArr1 += arr1[i]; sumArr2 += arr2[i]; # If both sumArr1 and sumArr2 # are even, pr0 and return if (sumArr1 % 2 == 0 and sumArr2 % 2 == 0): print(0); return; # If both sumArr1 and sumArr2 # are odd and check for a pair # with sum odd sum if (sumArr1 % 2 != 0 and sumArr2 % 2 != 0): # Stores if a pair with # odd sum exists or not flag = -1; # Traverse the array for i in range(n): # If a pair exists with odd # sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1): flag = 1; break; # Print the answer and return print(flag); return; # For all other cases, pr-1 print(-1); # Driver code if __name__ == '__main__': arr1 = [11, 14, 20, 2]; arr2 = [5, 9, 6, 3]; N = len(arr1); # Function Call minimumSwaps(arr1, arr2, N); # This code is contributed by 29AjayKumar
C#
// C# program to implement // the above approach using System; class GFG{ // Function to count the minimum swaps // of same-indexed elements from arrays // arr1[] and arr2[] required to make // the sum of both the arrays even static void minimumSwaps(int[] arr1, int[] arr2, int n) { // Store the sum of elements of // the array arr1 and arr2 respectively int sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for(int i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { Console.Write(0); return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not int flag = -1; // Traverse the array for(int i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1) { flag = 1; break; } } // Print the answer and return Console.Write(flag); return; } // For all other cases, print -1 Console.Write(-1); } // Driver code public static void Main() { int[] arr1 = { 11, 14, 20, 2 }; int[] arr2 = { 5, 9, 6, 3 }; int N = arr1.Length; // Function Call minimumSwaps(arr1, arr2, N); } } // This code is contributed by susmitakundugoaldanga
Javascript
<script> // Javascript program for the above approach // Function to count the minimum swaps // of same-indexed elements from arrays // arr1[] and arr2[] required to make // the sum of both the arrays even function minimumSwaps(arr1, arr2, n) { // Store the sum of elements of // the array arr1 and arr2 respectively let sumArr1 = 0, sumArr2 = 0; // Store the array sum of both the arrays for(let i = 0; i < n; ++i) { sumArr1 += arr1[i]; sumArr2 += arr2[i]; } // If both sumArr1 and sumArr2 // are even, print 0 and return if (sumArr1 % 2 == 0 && sumArr2 % 2 == 0) { document.write(0); return; } // If both sumArr1 and sumArr2 // are odd and check for a pair // with sum odd sum if (sumArr1 % 2 != 0 && sumArr2 % 2 != 0) { // Stores if a pair with // odd sum exists or not let flag = -1; // Traverse the array for(let i = 0; i < n; ++i) { // If a pair exists with odd // sum, set flag = 1 if ((arr1[i] + arr2[i]) % 2 == 1) { flag = 1; break; } } // Print the answer and return document.write(flag); return; } // For all other cases, print -1 document.write(-1); } // Driver Code let arr1 = [ 11, 14, 20, 2 ]; let arr2 = [ 5, 9, 6, 3 ]; let N = arr1.length; // Function Call minimumSwaps(arr1, arr2, N); // This code is contributed by splevel62 </script>
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pushpendrayadav1057 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA