Inserciones mínimas para hacer XOR de un Array igual a la mitad de su suma

Posted on by Rudeus Greyrat

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: 
    1. Si X = 0 , simplemente inserte S en la array. Ahora, el XOR es S y la suma es 2S .
    2. 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *