Dada una array arr[] de enteros no negativos, la tarea es encontrar un entero X tal que (arr[0] XOR X) + (arr[1] XOR X) + … + arr[n – 1] XOR X es mínimo posible.
Ejemplos:
Entrada: arr[] = {3, 9, 6, 2, 4}
Salida: X = 2, Suma = 22
Entrada: arr[] = {6, 56, 78, 34}
Salida: X = 2, Suma = 170
Enfoque: Verificaremos el bit ‘i’ de cada número de la array en representación binaria y contaremos los números que contengan ese bit ‘i’ establecido en ‘1’ porque estos bits establecidos contribuirán a maximizar la suma en lugar de minimizarla. Entonces, tenemos que hacer que este conjunto ‘i’ th bit sea ‘0’ si el conteo es mayor que N/2 y si el conteo es menor que N/2, entonces los números que tienen ‘i’ th bit configurado son menores y por lo tanto no afectará la respuesta. De acuerdo con la operación XOR en dos bits, sabemos que cuando A XOR B y A y B son iguales, el resultado es ‘0’, por lo que convertiremos ese ‘i’ enésimo bit en nuestro número (num) en ‘ 1’, de modo que (1 XOR 1) dará ‘0’ y minimizará la suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
// Function to find an integer X such that
// the sum of all the array elements after
// getting XORed with X is minimum
void findX(int arr[], int n)
{
// Finding Maximum element of array
int* itr = max_element(arr, arr + n);
// Find Maximum number of bits required
// in the binary representation
// of maximum number
// so log2 is calculated
int p = log2(*itr) + 1;
// Running loop from p times which is
// the number of bits required to represent
// all the elements of the array
int X = 0;
for (int i = 0; i < p; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
// If the bits in same position are set
// then count
if (arr[j] & (1 << i)) {
count++;
}
}
// If count becomes greater than half of
// size of array then we need to make
// that bit '0' by setting X bit to '1'
if (count > (n / 2)) {
// Again using shift operation to calculate
// the required number
X += 1 << i;
}
}
// Calculate minimized sum
long long int sum = 0;
for (int i = 0; i < n; i++)
sum += (X ^ arr[i]);
// Print solution
cout << "X = " << X << ", Sum = " << sum;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
findX(arr, n);
return 0;
}
Java
// Java implementation of above approach
import java.lang.Math;
import java.util.*;
class GFG
{
// Function to find an integer X such that
// the sum of all the array elements after
// getting XORed with X is minimum
public static void findX(int[] a, int n)
{
// Finding Maximum element of array
Collections.sort(Arrays.asList(a), null);
int itr = a[n-1];
// Find Maximum number of bits required
// in the binary representation
// of maximum number
// so log2 is calculated
int p = (int)(Math.log(itr)/Math.log(2)) + 1;
// Running loop from p times which is
// the number of bits required to represent
// all the elements of the array
int x = 0;
for (int i = 0; i < p; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
// If the bits in same position are set
// then count
if ((a[j] & (1 << i)) != 0)
count++;
}
// If count becomes greater than half of
// size of array then we need to make
// that bit '0' by setting X bit to '1'
if (count > (n / 2))
{
// Again using shift operation to calculate
// the required number
x += 1 << i;
}
}
// Calculate minimized sum
long sum = 0;
for (int i = 0; i < n; i++)
sum += (x ^ a[i]);
// Print solution
System.out.println("X = " + x + ", Sum = " + sum);
}
// Driver Code
public static void main(String[] args)
{
int[] a = {2, 3, 4, 5, 6};
int n = a.length;
findX(a, n);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python 3 implementation of the approach
from math import log2
# Function to find an integer X such that
# the sum of all the array elements after
# getting XORed with X is minimum
def findX(arr, n):
# Finding Maximum element of array
itr = arr[0]
for i in range(len(arr)):
# Find Maximum number of bits required
# in the binary representation
# of maximum number
# so log2 is calculated
if(arr[i] > itr):
itr = arr[i]
p = int(log2(itr)) + 1
# Running loop from p times which is
# the number of bits required to represent
# all the elements of the array
X = 0
for i in range(p):
count = 0
for j in range(n):
# If the bits in same position are set
# then increase count
if (arr[j] & (1 << i)):
count += 1
# If count becomes greater than half of
# size of array then we need to make
# that bit '0' by setting X bit to '1'
if (count > int(n / 2)):
# Again using shift operation to calculate
# the required number
X += 1 << i
# Calculate minimized sum
sum = 0
for i in range(n):
sum += (X ^ arr[i])
# Print solution
print("X =", X, ", Sum =", sum)
# Driver code
if __name__=='__main__':
arr = [2, 3, 4, 5, 6]
n = len(arr)
findX(arr, n)
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of above approach
using System;
using System.Linq;
class GFG
{
// Function to find an integer X such that
// the sum of all the array elements after
// getting XORed with X is minimum
public static void findX(int[] a, int n)
{
// Finding Maximum element of array
int itr = a.Max();
// Find Maximum number of bits required
// in the binary representation
// of maximum number
// so log2 is calculated
int p = (int) Math.Log(itr, 2) + 1;
// Running loop from p times which is
// the number of bits required to represent
// all the elements of the array
int x = 0;
for (int i = 0; i < p; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
// If the bits in same position are set
// then count
if ((a[j] & (1 << i)) != 0)
count++;
}
// If count becomes greater than half of
// size of array then we need to make
// that bit '0' by setting X bit to '1'
if (count > (n / 2))
{
// Again using shift operation to calculate
// the required number
x += 1 << i;
}
}
// Calculate minimized sum
long sum = 0;
for (int i = 0; i < n; i++)
sum += (x ^ a[i]);
// Print solution
Console.Write("X = " + x + ", Sum = " + sum);
}
// Driver Code
public static void Main(String[] args)
{
int[] a = {2, 3, 4, 5, 6};
int n = a.Length;
findX(a, n);
}
}
// This code is contributed by ravikishor
Javascript
<script>
// Javascript implementation of the approach
// Function to find an integer X such that
// the sum of all the array elements after
// getting XORed with X is minimum
function findX(arr, n)
{
// Finding Maximum element of array
let itr = Math.max(...arr);
// Find Maximum number of bits required
// in the binary representation
// of maximum number
// so log2 is calculated
let p = parseInt(Math.log(itr) / Math.log(2)) + 1;
// Running loop from p times which is
// the number of bits required to represent
// all the elements of the array
let X = 0;
for (let i = 0; i < p; i++) {
let count = 0;
for (let j = 0; j < n; j++) {
// If the bits in same position are set
// then count
if (arr[j] & (1 << i)) {
count++;
}
}
// If count becomes greater than half of
// size of array then we need to make
// that bit '0' by setting X bit to '1'
if (count > parseInt(n / 2)) {
// Again using shift
// operation to calculate
// the required number
X += 1 << i;
}
}
// Calculate minimized sum
let sum = 0;
for (let i = 0; i < n; i++)
sum += (X ^ arr[i]);
// Print solution
document.write("X = " + X + ", Sum = " + sum);
}
// Driver code
let arr = [ 2, 3, 4, 5, 6 ];
let n = arr.length;
findX(arr, n);
</script>
Producción:
X = 6, Sum = 14
Complejidad de tiempo: O(N * log(A))
Espacio auxiliar: O(1)