Dada una array desordenada que contiene un número par de ocurrencias para todos los números excepto dos números. Encuentre los dos números que tienen ocurrencias impares en O(n) complejidad de tiempo y O(1) espacio adicional.
Ejemplos:
Input: {12, 23, 34, 12, 12, 23, 12, 45}
Output: 34 and 45
Input: {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100}
Output: 100 and 5000
Input: {10, 20}
Output: 10 and 20
Un método ingenuo para resolver este problema es ejecutar dos bucles anidados. El ciclo externo selecciona un elemento y el ciclo interno cuenta el número de ocurrencias del elemento seleccionado. Si el recuento de ocurrencias es impar, imprima el número. La complejidad temporal de este método es O(n^2).
Podemos usar la clasificación para obtener los números impares que ocurren en el tiempo O (nLogn). Primero ordene los números usando un algoritmo de clasificación O(nLogn) como Merge Sort, Heap Sort… etc. Una vez que la array esté ordenada, todo lo que tenemos que hacer es un escaneo lineal de la array e imprimir el número impar que aparece.
También podemos usar hash . Cree una tabla hash vacía que tendrá elementos y sus recuentos. Elija todos los elementos de la array de entrada uno por uno. Busque el elemento seleccionado en la tabla hash. Si el elemento se encuentra en la tabla hash, incremente su conteo en la tabla. Si no se encuentra el elemento, ingréselo en la tabla hash con un conteo de 1. Después de ingresar todos los elementos en la tabla hash, escanee la tabla hash e imprima los elementos con un conteo impar. Este enfoque puede tomar O(n) tiempo en promedio, pero requiere O(n) espacio extra.
Solución de tiempo AO(n) y espacio extra O(1) usando XOR:
Sean x e y los dos números impares que aparecen. Usamos XOR bit a bit para obtener x e y. Intentamos hacer 2 grupos tales que x e y vayan a grupos diferentes. Por ejemplo, [a, a, b, b, x ], . Entonces el problema se convertirá en «Encontrar ‘un’ número con aparición impar en una array no ordenada», que se convierte en un problema simple y se resolverá usando XOR. A continuación se muestran los pasos para agrupar x e y de manera diferente.
1. El primer paso es hacer XOR de todos los elementos presentes en la array . XOR de todos los elementos nos da XOR de x e y debido a las siguientes propiedades de la operación XOR.
1) XOR de cualquier número n consigo mismo nos da 0, es decir, n ^ n = 0
2) XOR de cualquier número n con 0 nos da n, es decir, n ^ 0 = n
3) XOR es acumulativo y asociativo.
Entonces tenemos XOR de x e y después del primer paso, en forma decimal. Por ejemplo, 5 ^ 6 devuelve 3, que se calcula en forma de bits como 101 ^ 110 = 011. Sea xor2 el ‘valor’ de XOR. Cada bit Set** en xor2 indica que ‘los bits correspondientes en x e y tienen valores diferentes entre sí’ (propiedad XOR: ‘1 cuando los bits son diferentes’).
** ( Los bits establecidos son 1 en forma binaria. Por ejemplo, 101 tiene 2 bits establecidos (1), en el índice 0 y en el índice 2).
Por ejemplo, si x = 6 (0110) e y = 15 (1111), entonces xor2 será (1001), los dos bits establecidos en xor2 indican que los bits correspondientes en x e y son diferentes, en el índice 0 y en el 3. indexar ambos.
2. En el segundo paso, elegimos un bit fijo de xor2. La idea es usar el hecho de que xor2 es ‘1’ en índices donde los bits de x e y son diferentes. Entonces, separamos x e y en diferentes grupos, junto con el resto de los números de la lista, en función de si el número tiene el mismo conjunto de bits o no.
Elegimos el bit establecido más a la derecha de xor2, ya que es fácil obtener el bit establecido más a la derecha de un número (magia de bits). Si hacemos AND bit a bit un número con su contraparte negativa, obtenemos el bit establecido más a la derecha. (solo una propiedad basada en la observación, recuerda). Entonces, (xor2) y (-xor2) nos darán el bit de ajuste correcto. Encuentra (-número) por complemento a 2, es decir ((complemento a 1) +1). También se puede escribir como (~número)+1.
a) Ejemplo de complemento a 2 :
7 es 00111 (cualquier número de ceros anteriores). El complemento a 1 se obtiene volteando bits, 11000. Luego suma 1, por lo que el complemento a 2 de 7 es 11001 . Dado que el primer bit es 1, es un no negativo.
(-1)*16 + 1*8 +1*1 = -7
b) Ejemplo de (número) y (-número) = bit establecido a la derecha :
Continuando con el ejemplo de 7, 7 es 00111 y -7 es 11001, 7 y -7 es 00001. Entonces, el bit más a la derecha de 7 es 1.
Otro ejemplo con 12 y -12:
12 es 01100 ** y -12 se calcula cambiando dígitos y sumando 1. Entonces, 10011 y sumando 1 da 10100. 12 & -12, 01100 & 10100 da 00100 como bit establecido, que se devuelve como 4 en sistema decimal, también denominado Número de bit establecido aquí.
** (Dado que el número es de 32 bits, quedan 28 0 de ‘bit establecido a la izquierda’, pero tomar solo unos pocos está bien. Los números positivos tienen el bit 0 más a la izquierda y los negativos tienen 1)
3. En el tercer paso, separamos x e y en diferentes grupos : ahora sabemos que para el índice de bits del conjunto seleccionado, x e y tienen diferentes bits correspondientes. Si hacemos Y todos los números en la lista con el bit establecido, algunos darán 0 y otros darán 1. Pondremos todos los números que den ceros en un grupo y unos en otro. x e y caerán en diferentes grupos.
Explicado con un ejemplo: –
Por ejemplo, arr = [4, 2, 4, 10, 2, 3, 3, 12],
Paso 1) XOR de todos en arr cancelará todos los números repetidos. 10 ^12 será respuesta. 1010 ^ 1100 será 0110 que es xor=6.
Paso 2) El bit establecido es 10 de 01 10 de visualización. (número) & (-número) también es una forma rápida de encontrar el bit de ajuste correcto.
xor & (-xor) se pueden codificar directamente. 6 es 0110 y encontrar -6 cambiando dígitos y sumando 1, 1001 +1 = 1010.
Entonces, 6 Y -6 es esencialmente 0110 y 1010, es decir, 00 10 , es decir, 2: número de bit establecido.
Paso 3) AND de todos en la lista con 2 (Set bit no.) nos dará números que dan 1 o 0, y hacemos grupos.
[4, 4, 12] y [2, 10, 2, 3, 3], dando 0 y 1 respectivamente en AND con número de bit establecido.
Paso 4) XOR del 1er grupo nos dará x=12, x ^ y se conoce del 1er paso, es decir, 6. x ^(x ^y) nos dará y. 12 ^6 es 10.
x=12, y=10
Este paso funciona debido a las mismas propiedades de XOR. Todas las ocurrencias de un número irán en el mismo conjunto. XOR de todas las ocurrencias de un número que ocurren un número par de veces resultará en 0 en su conjunto. Y el xor de un conjunto será uno de los elementos que ocurren impares.
C++
// C++ Program to find the two odd occurring elements
#include <bits/stdc++.h>
using namespace std;
/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times. */
void printTwoOdd(int arr[], int size)
{
int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */
int set_bit_no; /* Will have only single set bit of xor2 */
int i;
int n = size - 2;
int x = 0, y = 0;
/* Get the xor of all elements in arr[]. The xor will basically
be xor of two odd occurring elements */
for(i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];
/* Get one set bit in the xor2. We get rightmost set bit
in the following line as it is easy to get */
set_bit_no = xor2 & ~(xor2-1);
/* Now divide elements in two sets:
1) The elements having the corresponding bit as 1.
2) The elements having the corresponding bit as 0. */
for(i = 0; i < size; i++)
{
/* XOR of first set is finally going to hold one odd
occurring number x */
if(arr[i] & set_bit_no)
x = x ^ arr[i];
/* XOR of second set is finally going to hold the other
odd occurring number y */
else
y = y ^ arr[i];
}
cout << "The two ODD elements are " << x << " & " << y;
}
/* Driver code */
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printTwoOdd(arr, arr_size);
return 0;
}
// This is code is contributed by rathbhupendra
C
// Program to find the two odd occurring elements
#include<stdio.h>
/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times. */
void printTwoOdd(int arr[], int size)
{
int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */
int set_bit_no; /* Will have only single set bit of xor2 */
int i;
int n = size - 2;
int x = 0, y = 0;
/* Get the xor of all elements in arr[]. The xor will basically
be xor of two odd occurring elements */
for(i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];
/* Get one set bit in the xor2. We get rightmost set bit
in the following line as it is easy to get */
set_bit_no = xor2 & ~(xor2-1);
/* Now divide elements in two sets:
1) The elements having the corresponding bit as 1.
2) The elements having the corresponding bit as 0. */
for(i = 0; i < size; i++)
{
/* XOR of first set is finally going to hold one odd
occurring number x */
if(arr[i] & set_bit_no)
x = x ^ arr[i];
/* XOR of second set is finally going to hold the other
odd occurring number y */
else
y = y ^ arr[i];
}
printf("\n The two ODD elements are %d & %d ", x, y);
}
/* Driver program to test above function */
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printTwoOdd(arr, arr_size);
getchar();
return 0;
}
Java
// Java program to find two odd
// occurring elements
import java.util.*;
class Main
{
/* Prints two numbers that occur odd
number of times. The function assumes
that the array size is at least 2 and
there are exactly two numbers occurring
odd number of times. */
static void printTwoOdd(int arr[], int size)
{
/* Will hold XOR of two odd occurring elements */
int xor2 = arr[0];
/* Will have only single set bit of xor2 */
int set_bit_no;
int i;
int n = size - 2;
int x = 0, y = 0;
/* Get the xor of all elements in arr[].
The xor will basically be xor of two
odd occurring elements */
for(i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];
/* Get one set bit in the xor2. We get
rightmost set bit in the following
line as it is easy to get */
set_bit_no = xor2 & ~(xor2-1);
/* Now divide elements in two sets:
1) The elements having the
corresponding bit as 1.
2) The elements having the
corresponding bit as 0. */
for(i = 0; i < size; i++)
{
/* XOR of first set is finally going
to hold one odd occurring number x */
if((arr[i] & set_bit_no)>0)
x = x ^ arr[i];
/* XOR of second set is finally going
to hold the other odd occurring number y */
else
y = y ^ arr[i];
}
System.out.println("The two ODD elements are "+
x + " & " + y);
}
// main function
public static void main (String[] args)
{
int arr[] = {4, 2, 4, 5, 2, 3, 3, 1};
int arr_size = arr.length;
printTwoOdd(arr, arr_size);
}
}
Python3
# Python3 program to find the
# two odd occurring elements
# Prints two numbers that occur odd
# number of times. The function assumes
# that the array size is at least 2 and
# there are exactly two numbers occurring
# odd number of times.
def printTwoOdd(arr, size):
# Will hold XOR of two odd occurring elements
xor2 = arr[0]
# Will have only single set bit of xor2
set_bit_no = 0
n = size - 2
x, y = 0, 0
# Get the xor of all elements in arr[].
# The xor will basically be xor of two
# odd occurring elements
for i in range(1, size):
xor2 = xor2 ^ arr[i]
# Get one set bit in the xor2. We get
# rightmost set bit in the following
# line as it is easy to get
set_bit_no = xor2 & ~(xor2 - 1)
# Now divide elements in two sets:
# 1) The elements having the corresponding bit as 1.
# 2) The elements having the corresponding bit as 0.
for i in range(size):
# XOR of first set is finally going to
# hold one odd occurring number x
if(arr[i] & set_bit_no):
x = x ^ arr[i]
# XOR of second set is finally going
# to hold the other odd occurring number y
else:
y = y ^ arr[i]
print("The two ODD elements are", x, "&", y)
# Driver Code
arr = [4, 2, 4, 5, 2, 3, 3, 1]
arr_size = len(arr)
printTwoOdd(arr, arr_size)
# This code is contributed by Anant Agarwal.
C#
// C# program to find two odd
// occurring elements
using System;
class main
{
// Prints two numbers that occur
// odd number of times. Function
// assumes that array size is at
// least 2 and there are exactly
// two numbers occurring odd number
// of times.
static void printTwoOdd(int []arr, int size) {
// Will hold XOR of two odd
//occurring elements
int xor2 = arr[0];
// Will have only single set
// bit of xor2
int set_bit_no;
int i;
//int n = size - 2;
int x = 0, y = 0;
// Get the xor of all the elements
// in arr[].The xor will basically
// be xor of two odd occurring
// elements
for(i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];
// Get one set bit in the xor2.
// We get rightmost set bit in
// the following line as it is
// to get.
set_bit_no = xor2 & ~(xor2-1);
// divide elements in two sets:
// 1) The elements having the
// corresponding bit as 1.
// 2) The elements having the
// corresponding bit as 0.
for(i = 0; i < size; i++)
{
// XOR of first set is finally
// going to hold one odd
// occurring number x
if((arr[i] & set_bit_no)>0)
x = x ^ arr[i];
// XOR of second set is finally
// going to hold the other
// odd occurring number y
else
y = y ^ arr[i];
}
Console.WriteLine("The two ODD elements are "+
x + " & " + y);
}
// main function
public static void Main()
{
int []arr = {4, 2, 4, 5, 2, 3, 3, 1};
int arr_size = arr.Length;
printTwoOdd(arr, arr_size);
}
}
//This code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to find the
// two odd occurring elements
/* Prints two numbers that occur
odd number of times. The
function assumes that the
array size is at least 2 and
there are exactly two numbers
occurring odd number of times. */
function printTwoOdd($arr, $size)
{
// Will hold XOR of two
// odd occurring elements
$xor2 = $arr[0];
// Will have only single
// set bit of xor2
$set_bit_no;
$i;
$n = $size - 2;
$x = 0;$y = 0;
// Get the xor of all elements
// in arr[]. The xor will basically
// be xor of two odd occurring
// elements
for($i = 1; $i < $size; $i++)
$xor2 = $xor2 ^ $arr[$i];
// Get one set bit in the xor2.
// We get rightmost set bit
// in the following line as
// it is easy to get
$set_bit_no = $xor2 & ~($xor2-1);
/* Now divide elements in two sets:
1) The elements having the
corresponding bit as 1.
2) The elements having the
corresponding bit as 0. */
for($i = 0; $i < $size; $i++)
{
/* XOR of first set is finally
going to hold one odd
occurring number x */
if($arr[$i] & $set_bit_no)
$x = $x ^ $arr[$i];
/* XOR of second set is finally
going to hold the other
odd occurring number y */
else
$y = $y ^ $arr[$i];
}
echo "The two ODD elements are ", $x, " & ", $y;
}
// Driver Code
$arr = array(4, 2, 4, 5, 2, 3, 3, 1);
$arr_size = sizeof($arr);
printTwoOdd($arr, $arr_size);
// This code is Contributed by Ajit
?>
Javascript
<script>
// Javascript program to find two odd
// occurring elements
// Prints two numbers that occur
// odd number of times. Function
// assumes that array size is at
// least 2 and there are exactly
// two numbers occurring odd number
// of times.
function printTwoOdd(arr, size)
{
// Will hold XOR of two odd
//occurring elements
let xor2 = arr[0];
// Will have only single set
// bit of xor2
let set_bit_no;
let i;
//int n = size - 2;
let x = 0, y = 0;
// Get the xor of all the elements
// in arr[].The xor will basically
// be xor of two odd occurring
// elements
for(i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];
// Get one set bit in the xor2.
// We get rightmost set bit in
// the following line as it is
// to get.
set_bit_no = xor2 & ~(xor2-1);
// divide elements in two sets:
// 1) The elements having the
// corresponding bit as 1.
// 2) The elements having the
// corresponding bit as 0.
for(i = 0; i < size; i++)
{
// XOR of first set is finally
// going to hold one odd
// occurring number x
if ((arr[i] & set_bit_no)>0)
x = x ^ arr[i];
// XOR of second set is finally
// going to hold the other
// odd occurring number y
else
y = y ^ arr[i];
}
document.write("The two ODD elements are "+ x +
" & " + y + "</br>");
}
// Driver code
let arr = [ 4, 2, 4, 5, 2, 3, 3, 1 ];
let arr_size = arr.length;
printTwoOdd(arr, arr_size);
// This code is contributed by divyesh072019
</script>
The two ODD elements are 5 & 1
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Otra solución sería usar el tiempo del mapa O (n) y la solución de espacio adicional O (n):
El espacio adicional O(n) se puede minimizar a O(1) tomando entradas directamente en el mapa en lugar de en la array.
La idea se explica a continuación usando comentarios en el código.
C++
// C++ Program to find the two odd occurring elements
#include <bits/stdc++.h>
using namespace std;
/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times.
*/
void printTwoOdd(int arr[], int size)
{
/*Create map and calculate frequency of array of
* elements using array.*/
unordered_map<int, int> m;
for (int i = 0; i < size; i++) {
m[arr[i]]++;
}
/*Traverse through the map and check if its second
element that is the frequency is odd or not.Then this
is the odd occurring element .Its is clearly mentioned
in problem that there are only two odd occurring
elements so this will print those two elements.*/
cout << "The two ODD elements are ";
for (auto& x : m) {
if (x.second % 2 != 0)
cout << x.first << ", ";
}
}
/* Driver code */
int main()
{
int arr[] = { 4, 2, 4, 5, 2, 3, 3, 1 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
printTwoOdd(arr, arr_size);
return 0;
}
// This is code is contributed by Abhishek
Java
// Java Program to find the two odd occurring elements
import java.util.*;
class GFG{
/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times.
*/
static void printTwoOdd(int arr[], int size)
{
/*Create map and calculate frequency of array of
* elements using array.*/
HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
for (int i = 0; i < size; i++) {
if(m.containsKey(arr[i])){
m.put(arr[i], m.get(arr[i])+1);
}
else{
m.put(arr[i], 1);
}
}
/*Traverse through the map and check if its second
element that is the frequency is odd or not.Then this
is the odd occurring element .Its is clearly mentioned
in problem that there are only two odd occurring
elements so this will print those two elements.*/
System.out.print("The two ODD elements are ");
for (Map.Entry<Integer,Integer> x : m.entrySet()) {
if (x.getValue() % 2 != 0)
System.out.print(x.getKey()+ ", ");
}
}
/* Driver code */
public static void main(String[] args)
{
int arr[] = { 4, 2, 4, 5, 2, 3, 3, 1 };
int arr_size = arr.length;
printTwoOdd(arr, arr_size);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the two odd occurring elements
""" Prints two numbers that occur odd number of times.
The function assumes that the array size is at least 2
and there are exactly two numbers occurring odd number
of times.
"""
def printTwoOdd(arr, size):
arr.sort()
# Create map and calculate frequency of array
# of elements using array.
m = {}
for i in range(size):
if arr[i] not in m:
m[arr[i]] = 0
m[arr[i]] += 1
"""Traverse through the map and check if its second
element that is the frequency is odd or not.Then this
is the odd occurring element .Its is clearly mentioned
in problem that there are only two odd occurring
elements so this will print those two elements."""
print("The two ODD elements are ", end = "")
for x in m:
if (m[x] % 2 != 0):
print(x, end = ", ")
# Driver code
arr = [ 4, 2, 4, 5, 2, 3, 3, 1 ]
arr_size = len(arr)
printTwoOdd(arr, arr_size)
# This code is contributed by shubhamsingh10
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG {
/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times.
*/
static void printTwoOdd(int[] arr, int size)
{
/*Create map and calculate frequency of array of
* elements using array.*/
Dictionary<int, int> m = new Dictionary<int, int>();
for (int i = 0; i < size; i++)
{
if (m.ContainsKey(arr[i]))
m[arr[i]]++;
else
m.Add(arr[i], 1);
}
/*Traverse through the map and check if its second
element that is the frequency is odd or not.Then this
is the odd occurring element .Its is clearly mentioned
in problem that there are only two odd occurring
elements so this will print those two elements.*/
Console.Write("The two ODD elements are ");
foreach (int x in m.Keys.ToList()){
if (m[x] % 2 != 0)
Console.Write(x + ", ");
}
}
// Driver Code
public static void Main (string[] args) {
int[] arr = { 4, 2, 4, 5, 2, 3, 3, 1 };
int arr_size = arr.Length;
printTwoOdd(arr, arr_size);
}
}
// This code is contributed by splevel62.
Javascript
<script>
// JavaScript Program to find the two odd occurring elements
/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times.
*/
function printTwoOdd(arr, size)
{
/*Create map and calculate frequency of array of
* elements using array.*/
let m = new Map();
for (let i = 0; i < size; i++) {
if(m.has(arr[i])){
m.set(arr[i], m.get(arr[i]) + 1)
}else{
m.set(arr[i], 1)
}
}
/*Traverse through the map and check if its second
element that is the frequency is odd or not.Then this
is the odd occurring element .Its is clearly mentioned
in problem that there are only two odd occurring
elements so this will print those two elements.*/
document.write("The two ODD elements are ");
let ar = []
for (let x of m) {
if (x[1] % 2 != 0)
ar.push(x[0])
}
document.write(`${ar.reverse()},`)
}
/* Driver code */
let arr = [ 4, 2, 4, 5, 2, 3, 3, 1 ];
let arr_size = arr.length;
printTwoOdd(arr, arr_size);
// This is code is contributed by gfgking
</script>
The two ODD elements are 1, 5,
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
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