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: 0
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: 1
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