Preguntado por SG
Dada una array en la que todos los números excepto dos se repiten una vez. (es decir, tenemos 2n+2 números y n números ocurren dos veces y los dos restantes ocurren una vez). Encuentra esos dos números de la manera más eficiente.
Método 1 (Usar clasificación)
Primero, clasifique todos los elementos. En la array ordenada, al comparar elementos adyacentes, podemos obtener fácilmente los elementos que no se repiten. La complejidad temporal de este método es O(nLogn)
Método 2 (Usar XOR)
Sean x e y los elementos que no se repiten que estamos buscando y arr[] sea la array de entrada. Primero, calcule el XOR de todos los elementos de la array.
xor = arr[0]^arr[1]^arr[2].....arr[n-1]
Todos los bits que se establecen en xor se establecerán en un elemento no repetitivo (x o y) y no en otros. Entonces, si tomamos cualquier conjunto de bits de xor y dividimos los elementos de la array en dos conjuntos: un conjunto de elementos con el mismo bit configurado y otro conjunto con el mismo bit sin configurar. Al hacerlo, obtendremos x en un conjunto e y en otro conjunto. Ahora, si hacemos XOR de todos los elementos en el primer conjunto, obtendremos el primer elemento que no se repite, y al hacer lo mismo en otros conjuntos, obtendremos el segundo elemento que no se repite.
Let us see an example.
arr[] = {2, 4, 7, 9, 2, 4}
1) Get the XOR of all the elements.
xor = 2^4^7^9^2^4 = 14 (1110)
2) Get a number which has only one set bit of the xor.
Since we can easily get the rightmost set bit, let us use it.
set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
Now set_bit_no will have only set as rightmost set bit of xor.
3) Now divide the elements in two sets and do xor of
elements in each set and we get the non-repeating
elements 7 and 9. Please see the implementation for this step.
Enfoque:
Paso 1: Xor todos los elementos de la array en una suma variable, por lo tanto, todos los elementos presentes dos veces en una array se eliminarán como, por ejemplo, 4 = «100» y si 4 x o 4 => «100» xor «100 ” por lo que la respuesta será “000”.
Paso 2: Por lo tanto, en la suma, la respuesta final será 3 x o 5, ya que tanto 2 como 4 son x o dando 0, por lo tanto, suma = “011” x o “101”, es decir, suma = “110” = 6.
Paso 3: Ahora tomaremos el Complemento a 2 de la suma, es decir (-suma) = “010”.
Paso 4: Ahora bit a bit Y los 2 de la suma con la suma, es decir, «110» y «010» dan la respuesta «010» (Apunte a bit a bit y es que queremos obtener un número que contenga solo el bit más a la derecha de la suma ).
Paso 5:bit a bit & todos los elementos del arreglo con esta suma obtenida, 2 = “010” & “010” = 2, 3 = “011” & “010” = “010”, 4 = “100” & “010” = “ 000”, 5 = “101” y “010” = “000”.
Paso 6: Como podemos ver, el bit a bit & de 2,3 > 0 será xor con sum1 y el bit a bit & de 4,5 resultará en 0, entonces será xor con sum2.
Paso 7: Como 2 está presente dos veces, obtener xor con sum1 dos veces solo almacena el resultado 3 y As 4 también está presente dos veces, por lo que obtener xor con sum2 cancelará su valor y, por lo tanto, solo 5 permanecerá allí.
Implementación:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
/* This function sets the values of
*x and *y to non-repeating elements
in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int* x, int* y)
{
/* Will hold Xor of all elements */
int Xor = arr[0];
/* Will have only single set bit of Xor */
int set_bit_no;
int i;
*x = 0;
*y = 0;
/* Get the Xor of all elements */
for (i = 1; i < n; i++)
Xor ^= arr[i];
/* Get the rightmost set bit in set_bit_no */
set_bit_no = Xor & ~(Xor - 1);
/* Now divide elements in two sets by
comparing rightmost set bit of Xor with bit
at same position in each element. */
for (i = 0; i < n; i++) {
/*Xor of first set */
if (arr[i] & set_bit_no)
*x = *x ^ arr[i];
/*Xor of second set*/
else {
*y = *y ^ arr[i];
}
}
}
/* Driver code */
int main()
{
int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = sizeof(arr) / sizeof(*arr);
int* x = new int[(sizeof(int))];
int* y = new int[(sizeof(int))];
get2NonRepeatingNos(arr, n, x, y);
cout << "The non-repeating elements are " << *x
<< " and " << *y;
}
// This code is contributed by rathbhupendra
C
// C program for above approach
#include <stdio.h>
#include <stdlib.h>
/* This function sets the values of
*x and *y to non-repeating elements
in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int* x, int* y)
{
/* Will hold Xor of all elements */
int Xor = arr[0];
/* Will have only single set bit of Xor */
int set_bit_no;
int i;
*x = 0;
*y = 0;
/* Get the Xor of all elements */
for (i = 1; i < n; i++)
Xor ^= arr[i];
/* Get the rightmost set bit in set_bit_no */
set_bit_no = Xor & ~(Xor - 1);
/* Now divide elements in two sets by
comparing rightmost set bit of Xor with bit
at same position in each element. */
for (i = 0; i < n; i++) {
/*Xor of first set */
if (arr[i] & set_bit_no)
*x = *x ^ arr[i];
/*Xor of second set*/
else {
*y = *y ^ arr[i];
}
}
}
/* Driver program to test above function */
int main()
{
int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 };
int* x = (int*)malloc(sizeof(int));
int* y = (int*)malloc(sizeof(int));
get2NonRepeatingNos(arr, 8, x, y);
printf("The non-repeating elements are %d and %d", *x,
*y);
getchar();
}
Java
// Java Program for above approach
public class UniqueNumbers {
// This function sets the values of
// *x and *y to non-repeating elements
// in an array arr[] of size n
public static void UniqueNumbers2(int[] arr, int n)
{
int sum = 0;
for (int i = 0; i < n; i++) {
// Xor all the elements of the array
// all the elements occurring twice will
// cancel out each other remaining
// two unique numbers will be xored
sum = (sum ^ arr[i]);
}
// Bitwise & the sum with it's 2's Complement
// Bitwise & will give us the sum containing
// only the rightmost set bit
sum = (sum & -sum);
// sum1 and sum2 will contains 2 unique
// elements initialized with 0 box
// number xored with 0 is number itself
int sum1 = 0;
int sum2 = 0;
// traversing the array again
for (int i = 0; i < arr.length; i++) {
// Bitwise & the arr[i] with the sum
// Two possibilities either result == 0
// or result > 0
if ((arr[i] & sum) > 0) {
// if result > 0 then arr[i] xored
// with the sum1
sum1 = (sum1 ^ arr[i]);
}
else {
// if result == 0 then arr[i]
// xored with sum2
sum2 = (sum2 ^ arr[i]);
}
}
// print the two unique numbers
System.out.println("The non-repeating elements are "
+ sum1 + " and " + sum2);
}
public static void main(String[] args)
{
int[] arr = new int[] { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = arr.length;
UniqueNumbers2(arr, n);
}
}
// This code is contributed by Parshav Nahta
Python3
# Python3 program for above approach
# This function sets the values of
# *x and *y to non-repeating elements
# in an array arr[] of size n
def UniqueNumbers2(arr, n):
sums = 0
for i in range(0, n):
# Xor all the elements of the array
# all the elements occurring twice will
# cancel out each other remaining
# two unique numbers will be xored
sums = (sums ^ arr[i])
# Bitwise & the sum with it's 2's Complement
# Bitwise & will give us the sum containing
# only the rightmost set bit
sums = (sums & -sums)
# sum1 and sum2 will contains 2 unique
# elements initialized with 0 box
# number xored with 0 is number itself
sum1 = 0
sum2 = 0
# Traversing the array again
for i in range(0, len(arr)):
# Bitwise & the arr[i] with the sum
# Two possibilities either result == 0
# or result > 0
if (arr[i] & sums) > 0:
# If result > 0 then arr[i] xored
# with the sum1
sum1 = (sum1 ^ arr[i])
else:
# If result == 0 then arr[i]
# xored with sum2
sum2 = (sum2 ^ arr[i])
# Print the two unique numbers
print("The non-repeating elements are ",
sum1, " and ", sum2)
# Driver Code
if __name__ == "__main__":
arr = [2, 3, 7, 9, 11, 2, 3, 11]
n = len(arr)
UniqueNumbers2(arr, n)
# This code is contributed by akhilsaini
C#
// C# program for above approach
using System;
class GFG {
// This function sets the values of
// *x and *y to non-repeating elements
// in an array arr[] of size n
static void UniqueNumbers2(int[] arr, int n)
{
int sum = 0;
for (int i = 0; i < n; i++) {
// Xor all the elements of the array
// all the elements occurring twice will
// cancel out each other remaining
// two unique numbers will be xored
sum = (sum ^ arr[i]);
}
// Bitwise & the sum with it's 2's Complement
// Bitwise & will give us the sum containing
// only the rightmost set bit
sum = (sum & -sum);
// sum1 and sum2 will contains 2 unique
// elements initialized with 0 box
// number xored with 0 is number itself
int sum1 = 0;
int sum2 = 0;
// Traversing the array again
for (int i = 0; i < arr.Length; i++) {
// Bitwise & the arr[i] with the sum
// Two possibilities either result == 0
// or result > 0
if ((arr[i] & sum) > 0) {
// If result > 0 then arr[i] xored
// with the sum1
sum1 = (sum1 ^ arr[i]);
}
else {
// If result == 0 then arr[i]
// xored with sum2
sum2 = (sum2 ^ arr[i]);
}
}
// Print the two unique numbers
Console.WriteLine("The non-repeating "
+ "elements are " + sum1 + " and "
+ sum2);
}
// Driver Code
static public void Main()
{
int[] arr = { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = arr.Length;
UniqueNumbers2(arr, n);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program for above approach
// This function sets the values of
// *x and *y to non-repeating elements
// in an array arr[] of size n
function UniqueNumbers2(arr, n)
{
let sum = 0;
for(let i = 0; i < n; i++)
{
// Xor all the elements of the array
// all the elements occurring twice will
// cancel out each other remaining
// two unique numbers will be xored
sum = (sum ^ arr[i]);
}
// Bitwise & the sum with it's 2's Complement
// Bitwise & will give us the sum containing
// only the rightmost set bit
sum = (sum & -sum);
// sum1 and sum2 will contains 2 unique
// elements initialized with 0 box
// number xored with 0 is number itself
let sum1 = 0;
let sum2 = 0;
// Traversing the array again
for(let i = 0; i < arr.length; i++)
{
// Bitwise & the arr[i] with the sum
// Two possibilities either result == 0
// or result > 0
if ((arr[i] & sum) > 0)
{
// If result > 0 then arr[i] xored
// with the sum1
sum1 = (sum1 ^ arr[i]);
}
else
{
// If result == 0 then arr[i]
// xored with sum2
sum2 = (sum2 ^ arr[i]);
}
}
// Print the two unique numbers
document.write("The non-repeating " +
"elements are " + sum1 +
" and " + sum2);
}
let arr = [ 2, 3, 7, 9, 11, 2, 3, 11 ];
let n = arr.length;
UniqueNumbers2(arr, n);
// This code is contributed by vaibhavrabadiya117.
</script>
Producción
The non-repeating elements are 7 and 9
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Consulte la publicación a continuación para obtener una explicación detallada:
encuentre los dos números con ocurrencias impares en una array sin ordenar
Método 3 (Usar mapas)
En este método, simplemente contamos la frecuencia de cada elemento. Los elementos cuya frecuencia es igual a 1 es el número que no se repite. La solución se explica a continuación en el código:
C++
// C++ program for Find the two non-repeating elements in
// an array of repeating elements/ Unique Numbers 2
#include <bits/stdc++.h>
using namespace std;
/* This function prints the two non-repeating elements in an
* array of repeating elements*/
void get2NonRepeatingNos(int arr[], int n)
{
/*Create map and calculate frequency of array
elements.*/
map<int, int> m;
for (int i = 0; i < n; i++) {
m[arr[i]]++;
}
/*Traverse through the map and check if its second
element that is the frequency is 1 or not. If this is
1 than it is the non-repeating element print it.It is
clearly mentioned in problem that all numbers except
two are repeated once. So they will be printed*/
cout << "The non-repeating elements are ";
for (auto& x : m) {
if (x.second == 1) {
cout << x.first << " ";
}
}
}
/* Driver code */
int main()
{
int arr[] = { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
get2NonRepeatingNos(arr, n);
}
// This code is contributed by Abhishek
Java
/*package whatever //do not write package name here */
//Java program to find 2 non repeating elements
//in array that has pairs of numbers
import java.util.*;
import java.io.*;
class GFG {
//Method to print the 2 non repeating elements in an array
public static void print2SingleNumbers(int[] nums){
/*We use a TreeMap to store the elements
in the sorted order*/
TreeMap<Integer, Integer> map = new TreeMap<>();
int n = nums.length;
/*Iterate through the array and check if each
element is present or not in the map. If the
element is present, remove it from the array
otherwise add it to the map*/
for(int i = 0; i<n; i++){
if(map.containsKey(nums[i]))
map.remove(nums[i]);
else
map.put(nums[i],1);
}
System.out.println("The non-repeating integers are " + map.firstKey() + " " + map.lastKey());
}
//Driver code
public static void main (String[] args) {
int[] nums = new int[]{2,11,3,11,7,3,9,2};
print2SingleNumbers(nums);
}
//This code is contributed by Satya Anvesh R
}
Python3
# Python program for Find the two
# non-repeating elements in an array
# of repeating elements/ Unique Numbers 2
# This function prints the two non-repeating elements in an
# array of repeating elements
def get2NonRepeatingNos(arr, n):
# Create map and calculate frequency of array
# elements
m = {}
for i in range(n):
if(arr[i] not in m):
m[arr[i]] = 0
m[arr[i]] = m[arr[i]] + 1
# Traverse through the map and check if its second
# element that is the frequency is 1 or not. If this is
# 1 than it is the non-repeating element print it.It is
# clearly mentioned in problem that all numbers except
# two are repeated once. So they will be printed
print("The non-repeating elements are", end = " ")
for key,value in m.items():
if (value == 1):
print(key,end = " ")
# Driver code
arr = [ 2, 3, 7, 9, 11, 2, 3, 11 ]
n = len(arr)
get2NonRepeatingNos(arr, n)
# This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG {
// Method to print the 2 non repeating elements in an array
public static void print2SingleNumbers(int[] A)
{
/*We use a TreeMap to store the elements
in the sorted order*/
Dictionary<int, int> map = new Dictionary<int, int>();
int n = A.Length;
/*Iterate through the array and check if each
element is present or not in the map. If the
element is present, remove it from the array
otherwise add it to the map*/
for (int i = 0 ; i < n; i++)
{
if(map.ContainsKey(A[i]))
map.Remove(A[i]);
else
map.Add(A[i], 1);
}
Console.Write("The non-repeating integers are " );
foreach(KeyValuePair<int, int> it in map){
if (it.Value == 1) {
Console.Write(it.Key + " ");
}
}
}
// Driver Code
public static void Main(String[] args) {
int[] nums = new int[]{2, 11, 3, 11, 7, 3, 9, 2};
print2SingleNumbers(nums);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for Find the two non-repeating elements in
// an array of repeating elements/ Unique Numbers 2
/* This function prints the two non-repeating elements in an
* array of repeating elements*/
function get2NonRepeatingNos(arr, n)
{
/*Create map and calculate frequency of array
elements.*/
let m = new Map();
for (let i = 0; i < n; i++) {
if(!m.has(arr[i]))
{
m.set(arr[i],0);
}
m.set(arr[i],m.get(arr[i])+1);
}
/*Traverse through the map and check if its second
element that is the frequency is 1 or not. If this is
1 than it is the non-repeating element print it.It is
clearly mentioned in problem that all numbers except
two are repeated once. So they will be printed*/
document.write("The non-repeating elements are ");
for (let [key,value] of m) {
if (value == 1) {
document.write(key," ");
}
}
}
/* Driver code */
let arr = [ 2, 3, 7, 9, 11, 2, 3, 11 ];
let n = arr.length;
get2NonRepeatingNos(arr, n);
// This code is contributed by shinjanpatra
</script>
Producción
The non-repeating elements are 7 9
Complejidad de tiempo : O(nlogn)
Espacio auxiliar : O(n)
Método 4 (Conjuntos de uso):
En este método, verificamos si el elemento ya existe, si existe, lo eliminamos, de lo contrario, lo agregamos al conjunto.
Enfoque :
Paso 1 : Tome cada elemento y verifique si existe en el conjunto o no. Si existe, vaya al paso 3. Si no existe, vaya al paso 2.
Paso 2 : agregue el elemento al conjunto y vaya al paso 4.
Paso 3 : Retire el elemento del conjunto y vaya al paso 4.
Paso 4 : Imprime los elementos del conjunto.
Implementación:
C++
// C++ program to find 2 non repeating elements
// in array that has pairs of numbers
#include <bits/stdc++.h>
using namespace std;
// Method to print the 2 non repeating elements in an array
void print2SingleNumbers(int nums[], int n)
{
// Create a Map Set to store the numbers
multiset<int> set;
/*Iterate through the array and check if each
element is present or not in the set. If the
element is present, remove it from the array
otherwise add it to the set*/
for (int i = 0; i < n; i++) {
auto it = set.find(nums[i]);
if (it != set.end())
set.erase(it);
else
set.insert(nums[i]);
}
/*Since there will only be 2 non-repeating elements
we can directly print them*/
cout << "The 2 non repeating numbers are : "
<< *set.begin() << " " << *next(set.begin(), 1);
}
// Driver code
int main()
{
int nums[] = { 2, 3, 7, 9, 11, 2, 3, 11 };
int n = sizeof(nums) / sizeof(nums[0]);
print2SingleNumbers(nums, n);
}
// This code is contributed by phasing17
Java
/*package whatever //do not write package name here */
//Java program to find 2 non repeating elements
//in array that has pairs of numbers
import java.util.LinkedHashSet;
import java.util.Iterator;
import java.io.*;
class GFG {
//Method to print the 2 non repeating elements in an array
public static void print2SingleNumbers(int[] nums){
// Create a Map Set to store the numbers
LinkedHashSet<Integer> set = new LinkedHashSet<>();
int n = nums.length;
/*Iterate through the array and check if each
element is present or not in the set. If the
element is present, remove it from the array
otherwise add it to the set*/
for(int i = 0; i<n; i++){
if(set.contains(nums[i]))
set.remove(nums[i]);
else
set.add(nums[i]);
}
//Iterator is used to traverse through the set
Iterator<Integer> i = set.iterator();
/*Since there will only be 2 non-repeating elements
we can directly print them*/
System.out.println("The 2 non repeating numbers are : " + i.next() + " " + i.next());
}
//Driver code
public static void main (String[] args) {
int[] nums = new int[]{2, 3, 7, 9, 11, 2, 3, 11 };
print2SingleNumbers(nums);
}
//This code contributed by Satya Anvesh R
}
Python3
# Python3 code to find 2 non repeating elements
# in array that has pairs of numbers
# Method to print the 2 non repeating
# elements in an array
def print2SingleNumbers(nums):
# Create a set to store the numbers
set_ = set()
n = len(nums)
# Iterate through the array and check if each
# element is present or not in the set. If the
# element is present, remove it from the array
# otherwise add it to the set
for i in nums:
if i in set_:
set_.remove(i)
else:
set_.add(i)
# Since there will only be 2 non
# repeating elements we can
# directly print them
print("The 2 non repeating numbers are : " + " ".join(map(str, set_)))
# Driver Code
nums = [2, 3, 7, 9, 11, 2, 3, 11]
# Function Call
print2SingleNumbers(nums)
# This code is contributed by phasing17
C#
// C# program to find 2 non repeating elements
// in array that has pairs of numbers
using System;
using System.Collections.Generic;
class GFG {
// Method to print the 2 non repeating elements in an
// array
public static void print2SingleNumbers(int[] nums)
{
// Create a Map Set to store the numbers
HashSet<int> set = new HashSet<int>();
int n = nums.Length;
/*Iterate through the array and check if each
element is present or not in the set. If the
element is present, remove it from the array
otherwise add it to the set*/
for (int i = 0; i < n; i++) {
if (set.Contains(nums[i]))
set.Remove(nums[i]);
else
set.Add(nums[i]);
}
/*Since there will only be 2 non-repeating elements
we can directly print them*/
Console.Write("The 2 non repeating numbers are : ");
foreach(var val in set) Console.Write(val + " ");
}
// Driver code
public static void Main(string[] args)
{
int[] nums = new int[] { 2, 3, 7, 9, 11, 2, 3, 11 };
print2SingleNumbers(nums);
}
}
// This code is contributed by phasing17
Javascript
// JavaScript code to find 2 non repeating elements
// in array that has pairs of numbers
// Method to print the 2 non repeating
// elements in an array
function print2SingleNumbers(nums)
{
// Create a set to store the numbers
let set = new Set();
let n = nums.length;
// Iterate through the array and check if each
// element is present or not in the set. If the
// element is present, remove it from the array
// otherwise add it to the set
for (var i of nums)
{
if (set.has(i))
set.delete(i);
else
set.add(i);
}
// Since there will only be 2 non
// repeating elements we can
// directly print them
console.log("The 2 non repeating numbers are :", [...set].join(' '));
}
// Driver Code
let nums = [2, 3, 7, 9, 11, 2, 3, 11];
// Function Call
print2SingleNumbers(nums);
// This code is contributed by phasing17
Producción
The 2 non repeating numbers are : 7 9
C++
// C++ program for Find the two non-repeating elements in
// an array of repeating elements/ Unique Numbers 2
#include <bits/stdc++.h>
using namespace std;
/* This function prints the two non-repeating elements in an
* array of repeating elements*/
void get2NonRepeatingNos(int arr[], int n)
{
/*Create map and calculate frequency of array
elements.*/
// Create a Map Set to store the numbers
set<int> s;
for (int i = 0; i < n; i++)
{
/*Iterate through the array and check if each
element is present or not in the set. If the
element is present, remove it from the array
otherwise add it to the set*/
if (s.find(arr[i]) != s.end())
s.erase(arr[i]);
else
s.insert(arr[i]);
}
cout << "The 2 non repeating numbers are : ";
for (auto it : s)
cout << it << " ";
cout << endl;
}
/* Driver code */
int main()
{
int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};
int n = sizeof(arr) / sizeof(arr[0]);
get2NonRepeatingNos(arr, n);
}
// This code is contributed by Aditya kumar
Java
// Java code to implement the approach
import java.util.*;
class GFG {
/* This function prints the two non-repeating elements in an
* array of repeating elements*/
static void get2NonRepeatingNos(int arr[], int n)
{
/*Create map and calculate frequency of array
elements.*/
// Create a Map Set to store the numbers
HashSet<Integer> s = new HashSet<Integer>();
for (int i = 0; i < n; i++)
{
/*Iterate through the array and check if each
element is present or not in the set. If the
element is present, remove it from the array
otherwise add it to the set*/
if (s.contains(arr[i]))
s.remove(arr[i]);
else
s.add(arr[i]);
}
System.out.print("The 2 non repeating numbers are : ");
for (int it : s)
System.out.print(it + " ");
System.out.println();
}
// Driver code
public static void main (String[] args) {
int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};
int n = arr.length;
get2NonRepeatingNos(arr, n);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python program for Find the two non-repeating elements in
# an array of repeating elements/ Unique Numbers 2
# This function prints the two non-repeating elements in an
# array of repeating elements
def get2NonRepeatingNos(arr, n):
# Create a Set to store the numbers
s = set()
for i in range(n):
# Iterate through the array and check if each
# element is present or not in the set. If the
# element is present, remove it from the array
# otherwise add it to the set
if (arr[i] in s):
s.remove(arr[i])
else:
s.add(arr[i])
print("The 2 non repeating numbers are :",end=" ")
for it in s:
print(it,end=" ")
print()
# Driver code
arr = [2, 3, 7, 9, 11, 2, 3, 11]
n = len(arr)
get2NonRepeatingNos(arr, n)
# This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
/* This function prints the two non-repeating elements in an
* array of repeating elements*/
static void get2NonRepeatingNos(int[] arr, int n)
{
/*Create map and calculate frequency of array
elements.*/
// Create a Map Set to store the numbers\
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++)
{
/*Iterate through the array and check if each
element is present or not in the set. If the
element is present, remove it from the array
otherwise add it to the set*/
if (s.Contains(arr[i]))
s.Remove(arr[i]);
else
s.Add(arr[i]);
}
Console.Write("The 2 non repeating numbers are : ");
foreach (int it in s)
Console.Write(it + " ");
Console.WriteLine();
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = {2, 3, 7, 9, 11, 2, 3, 11};
int n = arr.Length;
get2NonRepeatingNos(arr, n);
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// JavaScript program for Find the two non-repeating elements in
// an array of repeating elements/ Unique Numbers 2
/* This function prints the two non-repeating elements in an
* array of repeating elements*/
function get2NonRepeatingNos(arr, n)
{
// Create a Set to store the numbers
let s = new Set();
for (let i = 0; i < n; i++)
{
/*Iterate through the array and check if each
element is present or not in the set. If the
element is present, remove it from the array
otherwise add it to the set*/
if (s.has(arr[i]))
s.delete(arr[i]);
else
s.add(arr[i]);
}
document.write("The 2 non repeating numbers are : ");
for (const it of s)
document.write(it," ");
document.write("</br>");
}
/* Driver code */
let arr = [2, 3, 7, 9, 11, 2, 3, 11];
let n = arr.length;
get2NonRepeatingNos(arr, n);
// This code is contributed by shinjanpatra
</script>
Producción
The 2 non repeating numbers are : 7 9
Complejidad de tiempo: O (nlogn)
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