Dada una array de enteros positivos, la tarea es encontrar el número mínimo de inserciones a realizar en la array, para hacer que el XOR de la array sea igual a la mitad de su suma, es decir, 2 * Xor de todos los elementos = Suma de todos los elementos
Ejemplos:
Entrada: arr[] = {1 2 3 4 5}
Salida: 1 16
Explicación:
En la array modificada {1 2 3 4 5 1 16},
Sum = 1 + 2 + 3 + 4 + 5 + 1 + 16 = 32
Xor = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 1 ^ 16 = 16
Y, 2 * 16 == 32 Por lo tanto, se cumple
la condición 2 * Xor de todos los elementos = Suma de todos los elementos .Entrada: 7 11 3 25 51 32 9 29
Salida: 17 184
Explicación:
En la array modificada { 7 11 3 25 51 32 9 29 17 184}
Suma = 7 + 11 + 3 + 25 + 51 + 32 + 9 + 29 + 17 + 184 = 368
Xor = 7 ^ 11 ^ 3 ^ 25 ^ 51 ^ 32 ^ 9 ^ 29 ^ 17 ^ 184 = 184
Y, 2 * 184 == 368
Así, la condición 2 * Xor de todos los elementos = Suma de todos elementos está satisfecho.
Enfoque:
para resolver el problema, debemos centrarnos en las dos propiedades básicas de XOR:
- A x o A = 0
- A x o 0 = A
Necesitamos seguir los siguientes pasos para resolver el problema:
- Calcule la Suma de todos los elementos de la array (S) y el Xor de todos los elementos (X). Si S == 2*X , no se requiere ningún cambio en la array. Imprime -1 para este caso.
- De lo contrario, haga lo siguiente:
- Si X = 0 , simplemente inserte S en la array. Ahora, el XOR es S y la suma es 2S .
- De lo contrario, agregue X a la array para que el nuevo Xor de la array sea igual a 0. Luego, inserte S+X en la array. Ahora, la Suma es 2(S+X) y el Xor es S+X
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to make XOR of // of all array elements equal // to half of its sum // by minimum insertions #include <bits/stdc++.h> using namespace std; // Function to make XOR of the // array equal to half of its sum int make_xor_half(vector<int>& arr) { int sum = 0, xr = 0; // Calculate the sum and // Xor of all the elements for (int a : arr) { sum += a; xr ^= a; } // If the required condition // satisfies already, return // the original array if (2 * xr == sum) return -1; // If Xor is already zero, // Insert sum if (xr == 0) { arr.push_back(sum); return 1; } // Otherwise, insert xr // and insert sum + xr arr.push_back(xr); arr.push_back(sum + xr); return 2; } // Driver Code int main() { int N = 7; vector<int> nums = { 3, 4, 7, 1, 2, 5, 6 }; int count = make_xor_half(nums); if (count == -1) cout << "-1" << endl; else if (count == 1) cout << nums[N] << endl; else cout << nums[N] << " " << nums[N + 1] << endl; return 0; }
Python3
# Python3 program to make XOR of # of all array elements equal to # half of its sum by minimum # insertions # Function to make XOR of the # array equal to half of its sum def make_xor_half(arr): sum = 0; xr = 0; # Calculate the sum and # Xor of all the elements for a in arr: sum += a; xr ^= a; # If the required condition # satisfies already, return # the original array if (2 * xr == sum): return -1; # If Xor is already zero, # Insert sum if (xr == 0): arr.append(sum); return 1; # Otherwise, insert xr # and insert sum + xr arr.append(xr); arr.append(sum + xr); return 2; # Driver code if __name__ == "__main__": N = 7; nums = [ 3, 4, 7, 1, 2, 5, 6 ]; count = make_xor_half(nums); if (count == -1): print("-1"); elif (count == 1): print(nums[N]); else: print(nums[N], nums[N + 1]); # This code is contributed by AnkitRai01
Java
// Java program to make XOR of all // array elements equal to half // of its sum by minimum insertions import java.util.*; class GFG{ // Function to make XOR of the // array equal to half of its sum static int make_xor_half(ArrayList<Integer> arr) { int sum = 0, xr = 0; // Calculate the sum and // Xor of all the elements for (int i = 0; i < arr.size(); i++) { int a = arr.get(i); sum += a; xr ^= a; } // If the required condition // satisfies already, return // the original array if (2 * xr == sum) return -1; // If Xor is already zero, // Insert sum if (xr == 0) { arr.add(sum); return 1; } // Otherwise, insert xr // and insert sum + xr arr.add(xr); arr.add(sum + xr); return 2; } // Driver code public static void main(String[] args) { int N = 7; ArrayList<Integer> nums = new ArrayList<Integer>( Arrays.asList(3, 4, 7, 1, 2, 5, 6)); int count = make_xor_half(nums); if (count == -1) System.out.print(-1 + "\n"); else if (count == 1) System.out.print(nums.get(N) + "\n"); else System.out.print(nums.get(N) + " " + nums.get(N + 1) + "\n"); } } // This code is contributed by Chitranayal
C#
// C# program to make XOR of all // array elements equal to half // of its sum by minimum insertions using System; using System.Collections; using System.Collections.Generic; class GFG{ // Function to make XOR of the // array equal to half of its sum static int make_xor_half(ArrayList arr) { int sum = 0, xr = 0; // Calculate the sum and // Xor of all the elements foreach(int a in arr) { sum += a; xr ^= a; } // If the required condition // satisfies already, return // the original array if (2 * xr == sum) return -1; // If Xor is already zero, // Insert sum if (xr == 0) { arr.Add(sum); return 1; } // Otherwise, insert xr // and insert sum + xr arr.Add(xr); arr.Add(sum + xr); return 2; } // Driver code public static void Main(string[] args) { int N = 7; ArrayList nums = new ArrayList(){ 3, 4, 7, 1, 2, 5, 6 }; int count = make_xor_half(nums); if (count == -1) Console.Write(-1 + "\n"); else if (count == 1) Console.Write(nums[N] + "\n"); else Console.Write(nums[N] + " " + nums[N + 1] + "\n"); } } // This code is contributed by rutvik_56
Javascript
<script> // Javascript Program to make XOR of // of all array elements equal // to half of its sum // by minimum insertions // Function to make XOR of the // array equal to half of its sum function make_xor_half(arr) { let sum = 0, xr = 0; // Calculate the sum and // Xor of all the elements for (let a = 0; a < arr.length; a++) { sum += arr[a]; xr ^= arr[a]; } // If the required condition // satisfies already, return // the original array if (2 * xr == sum) return -1; // If Xor is already zero, // Insert sum if (xr == 0) { arr.push(sum); return 1; } // Otherwise, insert xr // and insert sum + xr arr.push(xr); arr.push(sum + xr); return 2; } // Driver Code let N = 7; let nums = [ 3, 4, 7, 1, 2, 5, 6 ]; let count = make_xor_half(nums); if (count == -1) document.write("-1<br>"); else if (count == 1) document.write(nums[N] + "<br>"); else document.write(nums[N] + " " + nums[N + 1]); </script>
28
Complejidad de tiempo: O(N) donde N es el tamaño de la array.
Publicación traducida automáticamente
Artículo escrito por jesuswahrman y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA