주어진 XOR을 사용하여 모든 쌍을 계산합니다.
서로 다른 양의 정수 배열과 숫자 x가 주어지면 배열에서 XOR이 x와 같은 정수 쌍의 수를 찾습니다.
예:
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 에이 간단한 솔루션 각 요소를 순회하여 XOR이 x와 같은 다른 숫자가 있는지 확인하는 것입니다. 이 솔루션은 O(n 2 ) 시간. 안 효율적인 솔루션 이 문제에는 O(n) 시간이 걸립니다. 이 아이디어는 arr[i] ^ arr[j]가 x와 같다는 사실과 arr[i] ^ x가 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.
구현:
C++ // C++ program to Count all pair with given XOR // value x #include 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/cpp/unordered_set-in-cpp-stl/ 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/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 # 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/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 */
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/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>
산출
Count of pairs with given XOR = 1
시간 복잡도 : 에)
보조 공간: O(n)
중복을 어떻게 처리하나요?
입력 배열에 중복이 있으면 위의 효율적인 솔루션이 작동하지 않습니다. 예를 들어 위의 솔루션은 {2 2 5}와 {5 2 2}에 대해 서로 다른 결과를 생성합니다. 중복을 처리하기 위해 모든 요소의 발생 횟수를 저장합니다. unordered_set 대신 unordered_map을 사용합니다.
구현:
C++ // C++ program to Count all pair with given XOR // value x #include 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>
산출
Count of pairs with given XOR = 1
시간복잡도 : O(n)
보조 공간: O(n)
