Dada una array que contiene un número impar de ocurrencias para todos los números, excepto algunos elementos que están presentes un número par de veces. Encuentre los elementos que tienen ocurrencias pares en la array en O (n) complejidad de tiempo y O (1) espacio extra.
Suponga que la array contiene elementos en el rango de 0 a 63.
Ejemplos:
Input: [9, 12, 23, 10, 12, 12, 15, 23, 14, 12, 15] Output: 12, 23 and 15 Input: [1, 4, 7, 5, 9, 7, 3, 4, 6, 8, 3, 0, 3] Output: 4 and 7 Input: [4, 4, 10, 10, 4, 4, 4, 4, 10, 10] Output: 4 and 10
Un método simple sería atravesar la array y almacenar las frecuencias de sus elementos en un mapa. Más tarde, imprima los elementos que tienen par contar en el mapa. La solución toma tiempo O(n) pero requiere espacio adicional para almacenar frecuencias. A continuación se muestra un método interesante para resolver este problema utilizando operadores bit a bit.
Este método supone que los enteros largos largos se almacenan usando 64 bits. La idea es usar el operador XOR. Lo sabemos
1 XOR 1 = 0 1 XOR 0 = 1 0 XOR 1 = 1 0 XOR 0 = 0
Considere la siguiente entrada:
1, 4, 7, 5, 9, 7, 3, 4, 6, 8, 3, 0, 3
Si desplazamos a la izquierda 1 por el valor de cada elemento de la array y tomamos XOR de todos los elementos, obtendremos un entero binario inferior:
1101101011
Cada 1 en el i-ésimo índice desde la derecha representa una ocurrencia impar del elemento i. Y cada 0 en el i-ésimo índice de la derecha representa incluso o no ocurrencia del elemento i en la array.
0 está presente en la posición 2, 4 y 7 en el número binario anterior. Pero 2 no está presente en nuestra array. Entonces nuestra respuesta es 4 y 7.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ Program to find the even occurring elements
// in given array
#include <iostream>
using namespace std;
// Function to find the even occurring elements
// in given array
void printRepeatingEven(int arr[], int n)
{
long long _xor = 0L;
long long pos;
// do for each element of array
for( int i = 0; i < n; ++i)
{
// left-shift 1 by value of current element
pos = 1 << arr[i];
// Toggle the bit everytime element gets repeated
_xor ^= pos;
}
// Traverse array again and use _xor to find even
// occurring elements
for (int i = 0; i < n; ++i)
{
// left-shift 1 by value of current element
pos = 1 << arr[i];
// Each 0 in _xor represents an even occurrence
if (!(pos & _xor))
{
// print the even occurring numbers
cout << arr[i] << " ";
// set bit as 1 to avoid printing duplicates
_xor ^= pos;
}
}
}
// Driver code
int main()
{
int arr[] = { 9, 12, 23, 10, 12, 12, 15, 23,
14, 12, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
printRepeatingEven(arr, n);
return 0;
}
Java
// Java Program to find the even occurring
// elements in given array
class GFG
{
// Function to find the even occurring
// elements in given array
static void printRepeatingEven(int arr[],
int n)
{
long _xor = 0L;
long pos;
// do for each element of array
for (int i = 0; i < n; ++i)
{
// left-shift 1 by value of
// current element
pos = 1 << arr[i];
// Toggle the bit everytime
// element gets repeated
_xor ^= pos;
}
// Traverse array again and use _xor
// to find even occurring elements
for (int i = 0; i < n; ++i)
{
// left-shift 1 by value of
// current element
pos = 1 << arr[i];
// Each 0 in _xor represents
// an even occurrence
if (!((pos & _xor)!=0))
{
// print the even occurring numbers
System.out.print(arr[i] + " ");
// set bit as 1 to avoid
// printing duplicates
_xor ^= pos;
}
}
}
// Driver code
public static void main(String args[])
{
int arr[] = {9, 12, 23, 10, 12, 12,
15, 23, 14, 12, 15};
int n = arr.length;
printRepeatingEven(arr, n);
}
}
// This code is contributed
// by 29AjayKumar
C#
// C# Program to find the even occurring
// elements in given array
using System;
class GFG
{
// Function to find the even occurring
// elements in given array
static void printRepeatingEven(int[] arr,
int n)
{
long _xor = 0L;
long pos;
// do for each element of array
for (int i = 0; i < n; ++i)
{
// left-shift 1 by value of
// current element
pos = 1 << arr[i];
// Toggle the bit everytime
// element gets repeated
_xor ^= pos;
}
// Traverse array again and use _xor
// to find even occurring elements
for (int i = 0; i < n; ++i)
{
// left-shift 1 by value of
// current element
pos = 1 << arr[i];
// Each 0 in _xor represents
// an even occurrence
if (!((pos & _xor) != 0))
{
// print the even occurring numbers
Console.Write(arr[i] + " ");
// set bit as 1 to avoid
// printing duplicates
_xor ^= pos;
}
}
}
// Driver code
public static void Main()
{
int[] arr = {9, 12, 23, 10, 12, 12,
15, 23, 14, 12, 15};
int n = arr.Length;
printRepeatingEven(arr, n);
}
}
// This code is contributed
// by Mukul singh
PHP
<?php
// PHP Program to find the even
// occurring elements in given array
// Function to find the even
// occurring elements in given array
function printRepeatingEven($arr, $n)
{
$_xor = 0;
$pos;
// do for each element of array
for( $i = 0; $i < $n; ++$i)
{
// left-shift 1 by value
// of current element
$pos = 1 << $arr[$i];
// Toggle the bit everytime
// element gets repeated
$_xor ^= $pos;
}
// Traverse array again and
// use _xor to find even
// occurring elements
for ($i = 0; $i < $n; ++$i)
{
// left-shift 1 by value
// of current element
$pos = 1 << $arr[$i];
// Each 0 in _xor represents
// an even occurrence
if (!($pos & $_xor))
{
// print the even
// occurring numbers
echo $arr[$i], " ";
// set bit as 1 to avoid
// printing duplicates
$_xor ^= $pos;
}
}
}
// Driver code
$arr = array(9, 12, 23, 10, 12, 12,
15, 23, 14, 12, 15 );
$n = sizeof($arr);
printRepeatingEven($arr, $n);
// This code is contributed by aj_36
?>
Python 3
# Python 3 program to find the even # occurring elements in given array # Function to find the even occurring # elements in given array def printRepeatingEven(arr, n): axor = 0; # do for each element of array for i in range(0, n): # left-shift 1 by value of # current element pos = 1 << arr[i]; # Toggle the bit every time # element gets repeated axor ^= pos; # Traverse array again and use _xor # to find even occurring elements for i in range(0, n - 1): # left-shift 1 by value of # current element pos = 1 << arr[i]; # Each 0 in _xor represents an # even occurrence if (not(pos & axor)): # print the even occurring numbers print(arr[i], end = " "); # set bit as 1 to avoid printing # duplicates axor ^= pos; # Driver code arr = [9, 12, 23, 10, 12, 12, 15, 23, 14, 12, 15 ]; n = len(arr) ; printRepeatingEven(arr, n); # This code is contributed # by Shivi_Aggarwal
Javascript
<script>
// Javascript Program to find the even occurring
// elements in given array
// Function to find the even occurring
// elements in given array
function printRepeatingEven(arr, n)
{
let _xor = 0;
let pos;
// do for each element of array
for (let i = 0; i < n; ++i)
{
// left-shift 1 by value of
// current element
pos = 1 << arr[i];
// Toggle the bit everytime
// element gets repeated
_xor ^= pos;
}
// Traverse array again and use _xor
// to find even occurring elements
for (let i = 0; i < n; ++i)
{
// left-shift 1 by value of
// current element
pos = 1 << arr[i];
// Each 0 in _xor represents
// an even occurrence
if (!((pos & _xor)!=0))
{
// print the even occurring numbers
document.write(arr[i] + " ");
// set bit as 1 to avoid
// printing duplicates
_xor ^= pos;
}
}
}
// Driver Code
let arr = [9, 12, 23, 10, 12, 12,
15, 23, 14, 12, 15];
let n = arr.length;
printRepeatingEven(arr, n);
</script>
Producción :
12 23 15
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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