Étant donné un tableau d'entiers positifs distincts et un nombre x, trouvez le nombre de paires d'entiers dans le tableau dont XOR est égal à x.
Exemples :
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 UN Solution simple consiste à parcourir chaque élément et à vérifier s'il existe un autre nombre dont le XOR avec lui est égal à x. Cette solution prend O(n2) temps. Un solution efficace à ce problème prend un temps O(n). L'idée est basée sur le fait que arr[i] ^ arr[j] est égal à x si et seulement si arr[i] ^ x est égal à 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.
Mise en œuvre:
C++// C++ program to Count all pair with given XOR // value x #include
// 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/cpp/unordered_set-in-cpp-stl/ 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 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# 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/cpp/unordered_set-in-cpp-stl/ 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 */
<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(arrnx) { 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/cpp/unordered_set-in-cpp-stl/ 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>
Sortir
Count of pairs with given XOR = 1
Complexité temporelle : Sur)
Espace auxiliaire : O(n)
Comment gérer les doublons ?
La solution efficace ci-dessus ne fonctionne pas s'il y a des doublons dans le tableau d'entrée. Par exemple, la solution ci-dessus produit des résultats différents pour {2 2 5} et {5 2 2}. Pour gérer les doublons, nous stockons le nombre d'occurrences de tous les éléments. Nous utilisons unordered_map au lieu de unordered_set.
Mise en œuvre:
C++// C++ program to Count all pair with given XOR // value x #include
// 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<IntegerInteger> 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 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# 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<intint> m = new Dictionary<intint>(); 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
<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>
Sortir
Count of pairs with given XOR = 1
Complexité temporelle : O(n)
Espace auxiliaire : O(n)