Nos dan una array de n elementos. La tarea es hacer XOR de toda la array 0. Podemos hacer lo siguiente para lograr esto.
- Podemos seleccionar cualquiera de los elementos.
- Después de seleccionar un elemento, podemos incrementarlo o decrementarlo en 1.
Necesitamos encontrar el número mínimo de operaciones de incremento/decremento requeridas para que el elemento seleccionado haga que la suma XOR de toda la array sea cero.
Ejemplos:
Input : arr[] = {2, 4, 8}
Output : Element = 8,
Operation required = 2
Explanation : Select 8 as element and perform 2
time decrement on it. So that it
became 6, Now our array is {2, 4, 6}
whose XOR sum is 0.
Input : arr[] = {1, 1, 1, 1}
Output : Element = 1,
Operation required = 0
Explanation : Select any of 1 and you have already
your XOR sum = 0. So, no operation
required.
Enfoque ingenuo: seleccione un elemento y luego encuentre el XOR del resto de la array. Si ese elemento se vuelve igual al XOR obtenido, entonces nuestro XOR de toda la array debería convertirse en cero. Ahora, nuestro costo por eso será la diferencia absoluta entre el elemento seleccionado y el XOR obtenido. Este proceso de encontrar el costo se realizará para cada elemento y, por lo tanto, dará como resultado una Complejidad de tiempo de (n ^ 2).
Enfoque eficiente: encuentre el XOR de toda la array. Ahora, supongamos que hemos seleccionado el elemento arr[i], por lo que el costo requerido para ese elemento será absoluto (arr[i]-(XORsum^arr[i])). Calculando el mínimo de estos valores absolutos para cada elemento será nuestra operación mínima requerida también el elemento correspondiente a la operación mínima requerida será nuestro elemento seleccionado.
Implementación:
C++
// CPP to find min cost to make
// XOR of whole array zero
#include <bits/stdc++.h>
using namespace std;
// function to find min cost
void minCost(int arr[], int n)
{
int cost = INT_MAX;
int element;
// calculate XOR sum of array
int XOR = 0;
for (int i = 0; i < n; i++)
XOR ^= arr[i];
// find the min cost and element corresponding
for (int i = 0; i < n; i++) {
if (cost > abs((XOR ^ arr[i]) - arr[i])) {
cost = abs((XOR ^ arr[i]) - arr[i]);
element = arr[i];
}
}
cout << "Element = " << element << endl;
cout << "Operation required = " << abs(cost);
}
// driver program
int main()
{
int arr[] = { 2, 8, 4, 16 };
int n = sizeof(arr) / sizeof(arr[0]);
minCost(arr, n);
return 0;
}
Java
// JAVA program to find min cost to make
// XOR of whole array zero
import java.lang.*;
class GFG
{
// function to find min cost
static void minCost(int[] arr, int n)
{
int cost = Integer.MAX_VALUE;
int element=0;
// calculate XOR sum of array
int XOR = 0;
for (int i = 0; i < n; i++)
XOR ^= arr[i];
// find the min cost and element
// corresponding
for (int i = 0; i < n; i++) {
if (cost > Math.abs((XOR ^ arr[i])
- arr[i])) {
cost = Math.abs((XOR ^ arr[i]) -
arr[i]);
element = arr[i];
}
}
System.out.println("Element = " + element);
System.out.println("Operation required = "+
Math.abs(cost));
}
// driver program
public static void main (String[] args)
{
int[] arr = { 2, 8, 4, 16 };
int n = arr.length;
minCost(arr, n);
}
}
/* This code is contributed by Kriti Shukla */
Python3
# python to find min cost to make
# XOR of whole array zero
# function to find min cost
def minCost(arr,n):
cost = 999999;
# calculate XOR sum of array
XOR = 0;
for i in range(0, n):
XOR ^= arr[i];
# find the min cost and element
# corresponding
for i in range(0,n):
if (cost > abs((XOR ^ arr[i]) - arr[i])):
cost = abs((XOR ^ arr[i]) - arr[i])
element = arr[i]
print("Element = ", element)
print("Operation required = ", abs(cost))
# driver program
arr = [ 2, 8, 4, 16 ]
n = len(arr)
minCost(arr, n)
# This code is contributed by Sam007
C#
// C# program to find min cost to
// make XOR of whole array zero
using System;
class GFG
{
// function to find min cost
static void minCost(int []arr, int n)
{
int cost = int.MaxValue;
int element=0;
// calculate XOR sum of array
int XOR = 0;
for (int i = 0; i < n; i++)
XOR ^= arr[i];
// find the min cost and
// element corresponding
for (int i = 0; i < n; i++)
{
if (cost > Math.Abs((XOR ^ arr[i]) - arr[i]))
{
cost = Math.Abs((XOR ^ arr[i]) - arr[i]);
element = arr[i];
}
}
Console.WriteLine("Element = " + element);
Console.Write("Operation required = "+
Math.Abs(cost));
}
// Driver program
public static void Main ()
{
int []arr = {2, 8, 4, 16};
int n = arr.Length;
minCost(arr, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP to find min cost to make
// XOR of whole array zero
// function to find min cost
function minCost($arr, $n)
{
$cost = PHP_INT_MAX;
$element;
// calculate XOR sum of array
$XOR = 0;
for ($i = 0; $i < $n; $i++)
$XOR ^= $arr[$i];
// find the min cost and
// element corresponding
for ($i = 0; $i < $n; $i++)
{
if ($cost > abs(($XOR ^ $arr[$i]) -
$arr[$i]))
{
$cost = abs(($XOR ^ $arr[$i]) -
$arr[$i]);
$element = $arr[$i];
}
}
echo "Element = " , $element ,"\n";
echo "Operation required = " , abs($cost);
}
// Driver Code
$arr = array(2, 8, 4, 16) ;
$n = count($arr);
minCost($arr, $n);
// This code is contributed by vt_m.
?>
Javascript
<script>
// javascript to find min cost to make
// XOR of whole array zero
// function to find min cost
function minCost(arr, n)
{
var cost = 1000000000;
var element;
// calculate XOR sum of array
var XOR = 0;
for (var i = 0; i < n; i++)
XOR ^= arr[i];
// find the min cost and element corresponding
for (var i = 0; i < n; i++) {
var x= Math.abs((XOR ^ arr[i]) - arr[i])
if (cost > x) {
cost = x;
element = arr[i];
}
}
document.write( "Element = " + element + "<br>");
document.write( "Operation required = " + Math.abs(cost));
}
// driver program
var arr = [ 2, 8, 4, 16 ];
var n = arr.length;
minCost(arr, n);
</script>
Element = 16 Operation required = 2
Complejidad de tiempo : O(n)
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA