Dada una array de enteros positivos distintos y un número x, encuentre el número de pares de enteros en la array cuyo XOR es igual a x.
Ejemplos:
Input : arr[] = {5, 4, 10, 15, 7, 6}, x = 5
Output : 1
Explanation : (10 ^ 15) = 5
Input : arr[] = {3, 6, 8, 10, 15, 50}, x = 5
Output : 2
Explanation : (3 ^ 6) = 5 and (10 ^ 15) = 5
Una solución simple es recorrer cada elemento y verificar si hay otro número cuyo XOR con él sea igual a x. Esta solución toma O(n 2 ) tiempo. Una solución eficiente a este problema requiere O(n) tiempo. La idea se basa en el hecho de que arr[i] ^ arr[j] es igual a x si y solo si arr[i] ^ x es igual a arr[j].
1) Initialize result as 0. 2) Create an empty hash set "s". 3) Do following for each element arr[i] in arr[] (a) If x ^ arr[i] is in "s", then increment result by 1. (b) Insert arr[i] into the hash set "s". 3) return result.
Implementación:
C++
// C++ program to Count all pair with given XOR
// value x
#include<bits/stdc++.h>
using namespace std;
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
int xorPairCount(int arr[], int n, int x)
{
int result = 0; // Initialize result
// create empty set that stores the visiting
// element of array.
// Refer below post for details of unordered_set
// https://www.geeksforgeeks.org/unorderd_set-stl-uses/
unordered_set<int> s;
for (int i=0; i<n ; i++)
{
// If there exist an element in set s
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (s.find(x^arr[i]) != s.end())
result++;
// Make element visited
s.insert(arr[i]);
}
// return total count of pairs with XOR equal to x
return result;
}
// driver program
int main()
{
int arr[] = {5 , 4 ,10, 15, 7, 6};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 5;
cout << "Count of pairs with given XOR = "
<< xorPairCount(arr, n, x);
return 0;
}
Java
// Java program to Count all pair with
// given XOR value x
import java.util.*;
class GFG
{
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
static int xorPairCount(int arr[], int n, int x)
{
int result = 0; // Initialize result
// create empty set that stores the visiting
// element of array.
// Refer below post for details of unordered_set
// https://www.geeksforgeeks.org/unorderd_set-stl-uses/
HashSet<Integer> s = new HashSet<Integer>();
for (int i = 0; i < n; i++)
{
// If there exist an element in set s
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (s.contains(x ^ arr[i]) &&
(x ^ arr[i]) == (int) s.toArray()[s.size() - 1])
{
result++;
}
// Make element visited
s.add(arr[i]);
}
// return total count of
// pairs with XOR equal to x
return result;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {5, 4, 10, 15, 7, 6};
int n = arr.length;
int x = 5;
System.out.print("Count of pairs with given XOR = "
+ xorPairCount(arr, n, x));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to count all the pair
# with given xor
# Returns count of pairs in arr[0..n-1]
# with XOR value equals to x.
def xorPairCount(arr, n, x):
result = 0 # Initialize result
# create empty set that stores the
# visiting element of array.
s = set()
for i in range(0, n):
# If there exist an element in set s
# with XOR equals to x^arr[i], that
# means there exist an element such
# that the XOR of element with arr[i]
# is equal to x, then increment count.
if(x ^ arr[i] in s):
result = result + 1
# Make element visited
s.add(arr[i])
return result
# Driver Code
if __name__ == "__main__":
arr = [5, 4, 10, 15, 7, 6]
n = len(arr)
x = 5
print("Count of pair with given XOR = " +
str(xorPairCount(arr, n, x)))
# This code is contributed by Anubhav Natani
C#
// C# program to Count all pair with
// given XOR value x
using System;
using System.Collections.Generic;
class GFG
{
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
static int xorPairCount(int []arr, int n, int x)
{
int result = 0; // Initialize result
// create empty set that stores the visiting
// element of array.
// Refer below post for details of unordered_set
// https://www.geeksforgeeks.org/unorderd_set-stl-uses/
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++)
{
// If there exist an element in set s
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (s.Contains(x ^ arr[i]))
{
result++;
}
// Make element visited
s.Add(arr[i]);
}
// return total count of
// pairs with XOR equal to x
return result;
}
// Driver code
public static void Main()
{
int []arr = {5, 4, 10, 15, 7, 6};
int n = arr.Length;
int x = 5;
Console.WriteLine("Count of pairs with given XOR = "
+ xorPairCount(arr, n, x));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to Count all pair with
// given XOR value x
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
function xorPairCount(arr,n,x)
{
let result = 0; // Initialize result
// create empty set that stores the visiting
// element of array.
// Refer below post for details of unordered_set
// https://www.geeksforgeeks.org/unorderd_set-stl-uses/
let s = new Set();
for (let i = 0; i < n; i++)
{
// If there exist an element in set s
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (s.has(x ^ arr[i]) )
{
result++;
}
// Make element visited
s.add(arr[i]);
}
// return total count of
// pairs with XOR equal to x
return result;
}
// Driver code
let arr=[5, 4, 10, 15, 7, 6];
let n = arr.length;
let x = 5;
document.write("Count of pairs with given XOR = "
+ xorPairCount(arr, n, x));
// This code is contributed by unknown2108
</script>
Producción
Count of pairs with given XOR = 1
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
¿Cómo manejar los duplicados?
La solución eficiente anterior no funciona si hay duplicados en la array de entrada. Por ejemplo, la solución anterior produce resultados diferentes para {2, 2, 5} y {5, 2, 2}. Para manejar duplicados, almacenamos recuentos de ocurrencias de todos los elementos. Usamos unordered_map en lugar de unordered_set.
Implementación:
C++
// C++ program to Count all pair with given XOR
// value x
#include<bits/stdc++.h>
using namespace std;
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
int xorPairCount(int arr[], int n, int x)
{
int result = 0; // Initialize result
// create empty map that stores counts of
// individual elements of array.
unordered_map<int, int> m;
for (int i=0; i<n ; i++)
{
int curr_xor = x^arr[i];
// If there exist an element in map m
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (m.find(curr_xor) != m.end())
result += m[curr_xor];
// Increment count of current element
m[arr[i]]++;
}
// return total count of pairs with XOR equal to x
return result;
}
// driver program
int main()
{
int arr[] = {2, 5, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 0;
cout << "Count of pairs with given XOR = "
<< xorPairCount(arr, n, x);
return 0;
}
Java
// Java program to Count all pair with given XOR
// value x
import java.util.*;
class GFG
{
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
static int xorPairCount(int arr[], int n, int x)
{
int result = 0; // Initialize result
// create empty map that stores counts of
// individual elements of array.
Map<Integer,Integer> m = new HashMap<>();
for (int i = 0; i < n ; i++)
{
int curr_xor = x^arr[i];
// If there exist an element in map m
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (m.containsKey(curr_xor))
result += m.get(curr_xor);
// Increment count of current element
if(m.containsKey(arr[i]))
{
m.put(arr[i], m.get(arr[i]) + 1);
}
else{
m.put(arr[i], 1);
}
}
// return total count of pairs with XOR equal to x
return result;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {2, 5, 2};
int n = arr.length;
int x = 0;
System.out.println("Count of pairs with given XOR = "
+ xorPairCount(arr, n, x));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to Count all pair with
# given XOR value x
# Returns count of pairs in arr[0..n-1]
# with XOR value equals to x.
def xorPairCount(arr, n, x):
result = 0 # Initialize result
# create empty map that stores counts
# of individual elements of array.
m = dict()
for i in range(n):
curr_xor = x ^ arr[i]
# If there exist an element in map m
# with XOR equals to x^arr[i], that
# means there exist an element such that
# the XOR of element with arr[i] is equal
# to x, then increment count.
if (curr_xor in m.keys()):
result += m[curr_xor]
# Increment count of current element
if arr[i] in m.keys():
m[arr[i]] += 1
else:
m[arr[i]] = 1
# return total count of pairs
# with XOR equal to x
return result
# Driver Code
arr = [2, 5, 2]
n = len(arr)
x = 0
print("Count of pairs with given XOR = ",
xorPairCount(arr, n, x))
# This code is contributed by Mohit Kumar
C#
// C# program to Count all pair with given XOR
// value x
using System;
using System.Collections.Generic;
class GFG
{
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
static int xorPairCount(int []arr, int n, int x)
{
int result = 0; // Initialize result
// create empty map that stores counts of
// individual elements of array.
Dictionary<int,int> m = new Dictionary<int,int>();
for (int i = 0; i < n ; i++)
{
int curr_xor = x^arr[i];
// If there exist an element in map m
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (m.ContainsKey(curr_xor))
result += m[curr_xor];
// Increment count of current element
if(m.ContainsKey(arr[i]))
{
var val = m[arr[i]];
m.Remove(arr[i]);
m.Add(arr[i], val + 1);
}
else
{
m.Add(arr[i], 1);
}
}
// return total count of pairs with XOR equal to x
return result;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {2, 5, 2};
int n = arr.Length;
int x = 0;
Console.WriteLine("Count of pairs with given XOR = "
+ xorPairCount(arr, n, x));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to Count all pair with given XOR
// value x
// Returns count of pairs in arr[0..n-1] with XOR
// value equals to x.
function xorPairCount(arr, n, x)
{
let result = 0; // Initialize result
// create empty map that stores counts of
// individual elements of array.
let m = new Map();
for (let i = 0; i < n ; i++)
{
let curr_xor = x^arr[i];
// If there exist an element in map m
// with XOR equals to x^arr[i], that means
// there exist an element such that the
// XOR of element with arr[i] is equal to
// x, then increment count.
if (m.has(curr_xor))
result += m.get(curr_xor);
// Increment count of current element
if(m.has(arr[i]))
{
m.set(arr[i], m.get(arr[i]) + 1);
}
else{
m.set(arr[i], 1);
}
}
// return total count of pairs with XOR equal to x
return result;
}
// Driver program
let arr = [2, 5, 2];
let n = arr.length;
let x = 0;
document.write("Count of pairs with given XOR = "
+ xorPairCount(arr, n, x));
</script>
Producción
Count of pairs with given XOR = 1
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Nishant_singh(pintu) . 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.
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