Recuento de elementos que se insertarán para hacer que Array sume el doble del XOR de Array

Dada una array arr[] de tamaño N , la tarea es encontrar la cantidad mínima de elementos que deben insertarse en la array para que la suma de la array sea igual a dos veces el XOR de la array
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, 6} 
Salida:
Explicación: 
Xor = (1 ^ 2 ^ 3 ^ 6) = 6 y suma de la array = 12. 
La condición requerida (sum = 2 * Xor ) satisface. Así que no es necesario insertar más elementos.
Entrada: arr[] = {1, 2, 3} 
Salida:
Explicación: 
Xor = (1 ^ 2 ^ 3) = 0 y suma de la array = (1 + 2 + 3) = 6. 
Aquí, insertamos uno elemento {6} en la array. Ahora, NewXor = (0 ^ 6) = 6 y NewSum = (6 + 6) = 12. 
Por lo tanto, NewSum = 2*NewXor. 
Entonces, la condición dada se cumple. 
 

Enfoque: La idea es calcular los siguientes pasos para encontrar la respuesta: 
 

  • Inicialmente, encontramos la suma de la array y el XOR de la array .
  • Ahora comprobamos si la condición dada se cumple o no. Si satisface, imprima 0 ya que no necesitamos insertar ningún elemento.
  • Ahora, comprueba si el XOR es igual a 0 o no. Si es así, entonces el elemento que debe insertarse en la array es la suma de todos los elementos de la array.
  • Esto se debe a que, al insertar la suma, el nuevo XOR se convierte en (0 ^ suma = suma) y la suma de la array se convierte en suma + suma = 2 * suma. Por lo tanto la condición se cumple.
  • De lo contrario, agregamos dos elementos más que son XOR y (suma + XOR). Esto es porque: 
     

NuevoXor = (Xor ^ (suma + Xor) ^ Xor) = Suma + Xor. 
NuevaSuma = (Suma + (Suma + Xor) + Xor) = 2 * (Suma + Xor) = 2 * NuevaXor 
 

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program to find the count
// of elements to be inserted to
// make Array sum twice the XOR of Array
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number of elements that need to be
// inserted such that the sum of the
// elements of the array is twice
// the XOR of the array
void insert_element(int a[], int n)
{
     
    // Variable to store the
    // Xor of all the elements
    int Xor = 0;
 
    // Variable to store the
    // sum of all elements
    int Sum = 0;
     
    // Loop to find the Xor
    // and the sum of the array
    for(int i = 0; i < n; i++)
    { 
        Xor ^= a[i];
        Sum += a[i];
    }
     
    // If sum = 2 * Xor
    if(Sum == 2 * Xor)
    {
       
        // No need to insert
        // more elements
        cout << "0" << endl;
        return;
     }
   
    // We insert one more element
    // which is Sum
    if(Xor == 0)
    {
        cout << "1" << endl;
        cout << Sum << endl;
        return;
     }
 
    // We insert two more elements
    // Sum + Xor and Xor.
    int num1 = Sum + Xor;
     
    int num2 = Xor;
 
    // Print the number of elements
    // inserted in the array
    cout << "2";
 
    // Print the elements that are
    // inserted in the array
    cout << num1 << " "
         << num2 << endl; 
}
 
// Driver code
int main()
{   
    int a[] = {1, 2, 3};
    int n = sizeof(a) / sizeof(a[0]);
   
    insert_element(a, n);
}
 
// This code is contributed by chitranayal

Java

// Java program to find the count
// of elements to be inserted to
// make Array sum twice the XOR of Array
class GFG{
  
// Function to find the minimum
// number of elements that need to be
// inserted such that the sum of the
// elements of the array is twice
// the XOR of the array
static void insert_element(int a[], int n)
{
      
    // Variable to store the
    // Xor of all the elements
    int Xor = 0;
  
    // Variable to store the
    // sum of all elements
    int Sum = 0;
      
    // Loop to find the Xor
    // and the sum of the array
    for(int i = 0; i < n; i++)
    { 
        Xor ^= a[i];
        Sum += a[i];
    }
      
    // If sum = 2 * Xor
    if(Sum == 2 * Xor)
    {
        
        // No need to insert
        // more elements
        System.out.println("0");
        return;
     }
    
    // We insert one more element
    // which is Sum
    if(Xor == 0)
    {
        System.out.println("1");
        System.out.println(Sum);
        return;
     }
  
    // We insert two more elements
    // Sum + Xor and Xor.
    int num1 = Sum + Xor;
      
    int num2 = Xor;
  
    // Print the number of elements
    // inserted in the array
    System.out.print("2");
  
    // Print the elements that are
    // inserted in the array
    System.out.println(num1 + " " + num2);
}
  
// Driver code
public static void main(String[] args)
{   
    int a[] = {1, 2, 3};
    int n = a.length;
    
    insert_element(a, n);
}
}
 
// This code is contributed by rock_cool

Python3

# Python program to find the count
# of elements to be inserted to
# make Array sum twice the XOR of Array
 
# Function to find the minimum
# number of elements that need to be
# inserted such that the sum of the
# elements of the array is twice
# the XOR of the array
def insert_element(a, n):
     
    # Variable to store the
    # Xor of all the elements
    Xor = 0
 
    # Variable to store the
    # sum of all elements
    Sum = 0
     
    # Loop to find the Xor
    # and the sum of the array
    for i in range(n):
         
        Xor^= a[i]
        Sum+= a[i]
     
    # If sum = 2 * Xor
    if(Sum == 2 * Xor):
 
        # No need to insert
        # more elements
        print(0)
        return
 
    # We insert one more element
    # which is Sum
    if(Xor == 0):
        print(1)
        print(Sum)
        return
 
    # We insert two more elements
    # Sum + Xor and Xor.
    num1 = Sum + Xor
     
    num2 = Xor
 
    # Print the number of elements
    # inserted in the array
    print(2)
 
    # Print the elements that are
    # inserted in the array
    print(num1, num2)
     
         
# Driver code
if __name__ == "__main__":
     
    a = [1, 2, 3]
    n = len(a)
    insert_element(a, n)

C#

// C# program to find the count
// of elements to be inserted to
// make Array sum twice the XOR of Array
using System;
class GFG{
   
// Function to find the minimum
// number of elements that need to be
// inserted such that the sum of the
// elements of the array is twice
// the XOR of the array
static void insert_element(int[] a, int n)
{
       
    // Variable to store the
    // Xor of all the elements
    int Xor = 0;
   
    // Variable to store the
    // sum of all elements
    int Sum = 0;
       
    // Loop to find the Xor
    // and the sum of the array
    for(int i = 0; i < n; i++)
    { 
        Xor ^= a[i];
        Sum += a[i];
    }
       
    // If sum = 2 * Xor
    if(Sum == 2 * Xor)
    {
         
        // No need to insert
        // more elements
        Console.Write("0");
        return;
     }
     
    // We insert one more element
    // which is Sum
    if(Xor == 0)
    {
        Console.Write("1" + '\n');
        Console.Write(Sum);
        return;
     }
   
    // We insert two more elements
    // Sum + Xor and Xor.
    int num1 = Sum + Xor;
       
    int num2 = Xor;
   
    // Print the number of elements
    // inserted in the array
    Console.Write("2");
   
    // Print the elements that are
    // inserted in the array
    Console.Write(num1 + " " + num2);
}
   
// Driver code
public static void Main(string[] args)
{   
    int[] a = {1, 2, 3};
    int n = a.Length;
     
    insert_element(a, n);
}
}
  
// This code is contributed by Ritik Bansal

Javascript

<script>
 
    // Javascript program to find the count
    // of elements to be inserted to
    // make Array sum twice the XOR of Array
     
    // Function to find the minimum
    // number of elements that need to be
    // inserted such that the sum of the
    // elements of the array is twice
    // the XOR of the array
    function insert_element(a, n)
    {
 
        // Variable to store the
        // Xor of all the elements
        let Xor = 0;
 
        // Variable to store the
        // sum of all elements
        let Sum = 0;
 
        // Loop to find the Xor
        // and the sum of the array
        for(let i = 0; i < n; i++)
        {
            Xor ^= a[i];
            Sum += a[i];
        }
 
        // If sum = 2 * Xor
        if(Sum == 2 * Xor)
        {
 
            // No need to insert
            // more elements
            document.write("0" + "</br>");
            return;
         }
 
        // We insert one more element
        // which is Sum
        if(Xor == 0)
        {
            document.write("1" + "</br>");
            document.write(Sum + "</br>");
            return;
         }
 
        // We insert two more elements
        // Sum + Xor and Xor.
        let num1 = Sum + Xor;
 
        let num2 = Xor;
 
        // Print the number of elements
        // inserted in the array
        document.write("2" + "</br>");
 
        // Print the elements that are
        // inserted in the array
        document.write(num1 + " " + num2 + "</br>");
    }
 
    let a = [1, 2, 3];
    let n = a.length;
    
    insert_element(a, n);
     
</script>
Producción: 

1
6

 

Complejidad de tiempo: O (n), ya que estamos atravesando una vez en una array.

Complejidad espacial: O (1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

Artículo escrito por ghoshashis545 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 *