최소 XOR 값 쌍
GfG Practice에서 사용해 보세요. 
#practiceLinkDiv { 표시: 없음 !중요; }
산출
산출
산출
#practiceLinkDiv { 표시: 없음 !중요; } 정수 배열이 주어졌습니다. 최소 XOR 값을 갖는 배열에서 쌍을 찾습니다.
예:
Input : arr[] = {9 5 3} Output : 6 All pair with xor value (9 ^ 5) => 12 (5 ^ 3) => 6 (9 ^ 3) => 10. Minimum XOR value is 6 Input : arr[] = {1 2 3 4 5} Output : 1 Recommended Practice 최소 XOR 값 쌍 시도해 보세요! 에이 간단한 솔루션 주어진 배열의 모든 쌍을 생성하고 해당 값을 XOR 계산하는 것입니다. 마지막으로 최소 XOR 값을 반환합니다. 이 솔루션은 O(n 2 ) 시간.
구현:
C++ // C++ program to find minimum XOR value in an array. #include using namespace std ; // Returns minimum xor value of pair in arr[0..n-1] int minXOR ( int arr [] int n ) { int min_xor = INT_MAX ; // Initialize result // Generate all pair of given array for ( int i = 0 ; i < n ; i ++ ) for ( int j = i + 1 ; j < n ; j ++ ) // update minimum xor value if required min_xor = min ( min_xor arr [ i ] ^ arr [ j ]); return min_xor ; } // Driver program int main () { int arr [] = { 9 5 3 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < minXOR ( arr n ) < < endl ; return 0 ; }
Java // Java program to find minimum XOR value in an array. class GFG { // Returns minimum xor value of pair in arr[0..n-1] static int minXOR ( int arr [] int n ) { int min_xor = Integer . MAX_VALUE ; // Initialize result // Generate all pair of given array for ( int i = 0 ; i < n ; i ++ ) for ( int j = i + 1 ; j < n ; j ++ ) // update minimum xor value if required min_xor = Math . min ( min_xor arr [ i ] ^ arr [ j ] ); return min_xor ; } // Driver program public static void main ( String args [] ) { int arr [] = { 9 5 3 }; int n = arr . length ; System . out . println ( minXOR ( arr n )); } } // This code is contributed by Sumit Ghosh
Python3 # Python program to find minimum # XOR value in an array. # Function to find minimum XOR pair def minXOR ( arr n ): # Sort given array arr . sort (); min_xor = 999999 val = 0 # calculate min xor of # consecutive pairs for i in range ( 0 n - 1 ): for j in range ( i + 1 n - 1 ): # update minimum xor value # if required val = arr [ i ] ^ arr [ j ] min_xor = min ( min_xor val ) return min_xor # Driver program arr = [ 9 5 3 ] n = len ( arr ) print ( minXOR ( arr n )) # This code is contributed by Sam007.
C# // C# program to find minimum // XOR value in an array. using System ; class GFG { // Returns minimum xor value of // pair in arr[0..n-1] static int minXOR ( int [] arr int n ) { // Initialize result int min_xor = int . MaxValue ; // Generate all pair of given array for ( int i = 0 ; i < n ; i ++ ) for ( int j = i + 1 ; j < n ; j ++ ) // update minimum xor value if required min_xor = Math . Min ( min_xor arr [ i ] ^ arr [ j ]); return min_xor ; } // Driver program public static void Main () { int [] arr = { 9 5 3 }; int n = arr . Length ; Console . WriteLine ( minXOR ( arr n )); } } // This code is contributed by Sam007
PHP // PHP program to find minimum // XOR value in an array. // Returns minimum xor value // of pair in arr[0..n-1] function minXOR ( $arr $n ) { // Initialize result $min_xor = PHP_INT_MAX ; // Generate all pair of given array for ( $i = 0 ; $i < $n ; $i ++ ) for ( $j = $i + 1 ; $j < $n ; $j ++ ) // update minimum xor // value if required $min_xor = min ( $min_xor $arr [ $i ] ^ $arr [ $j ]); return $min_xor ; } // Driver Code $arr = array ( 9 5 3 ); $n = count ( $arr ); echo minXOR ( $arr $n ); // This code is contributed by anuj_67. ?>
JavaScript < script > // Javascript program to find // minimum XOR value in an array. // Returns minimum xor value of pair in arr[0..n-1] function minXOR ( arr n ) { // Initialize result let min_xor = Number . MAX_VALUE ; // Generate all pair of given array for ( let i = 0 ; i < n ; i ++ ) for ( let j = i + 1 ; j < n ; j ++ ) // update minimum xor value if required min_xor = Math . min ( min_xor arr [ i ] ^ arr [ j ]); return min_xor ; } // Driver program let arr = [ 9 5 3 ]; let n = arr . length ; document . write ( minXOR ( arr n )); < /script>
산출
6
공간 복잡도: O(1)
안 효율적인 솔루션 O(nlogn) 시간 안에 이 문제를 해결할 수 있습니다.
연산:
- 주어진 배열을 정렬
- 모든 연속 쌍에 대해 탐색하고 XOR을 확인합니다.
다음은 위의 접근 방식을 구현한 것입니다.
C++ #include using namespace std ; // Function to find minimum XOR pair int minXOR ( int arr [] int n ) { // Sort given array sort ( arr arr + n ); int minXor = INT_MAX ; int val = 0 ; // calculate min xor of consecutive pairs for ( int i = 0 ; i < n - 1 ; i ++ ) { val = arr [ i ] ^ arr [ i + 1 ]; minXor = min ( minXor val ); } return minXor ; } // Driver program int main () { int arr [] = { 9 5 3 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < minXOR ( arr n ) < < endl ; return 0 ; }
Java import java.util.Arrays ; class GFG { // Function to find minimum XOR pair static int minXOR ( int arr [] int n ) { // Sort given array Arrays . parallelSort ( arr ); int minXor = Integer . MAX_VALUE ; int val = 0 ; // calculate min xor of consecutive pairs for ( int i = 0 ; i < n - 1 ; i ++ ) { val = arr [ i ] ^ arr [ i + 1 ] ; minXor = Math . min ( minXor val ); } return minXor ; } // Driver program public static void main ( String args [] ) { int arr [] = { 9 5 3 }; int n = arr . length ; System . out . println ( minXOR ( arr n )); } } // This code is contributed by Sumit Ghosh
Python3 import sys # Function to find minimum XOR pair def minXOR ( arr n ): # Sort given array arr . sort () minXor = int ( sys . float_info . max ) val = 0 # calculate min xor of consecutive pairs for i in range ( 0 n - 1 ): val = arr [ i ] ^ arr [ i + 1 ]; minXor = min ( minXor val ); return minXor # Driver program arr = [ 9 5 3 ] n = len ( arr ) print ( minXOR ( arr n )) # This code is contributed by Sam007.
C# // C# program to find minimum // XOR value in an array. using System ; class GFG { // Function to find minimum XOR pair static int minXOR ( int [] arr int n ) { // Sort given array Array . Sort ( arr ); int minXor = int . MaxValue ; int val = 0 ; // calculate min xor of consecutive pairs for ( int i = 0 ; i < n - 1 ; i ++ ) { val = arr [ i ] ^ arr [ i + 1 ]; minXor = Math . Min ( minXor val ); } return minXor ; } // Driver program public static void Main () { int [] arr = { 9 5 3 }; int n = arr . Length ; Console . WriteLine ( minXOR ( arr n )); } } // This code is contributed by Sam007
PHP // Function to find minimum XOR pair function minXOR ( $arr $n ) { // Sort given array sort ( $arr ); $minXor = PHP_INT_MAX ; $val = 0 ; // calculate min xor // of consecutive pairs for ( $i = 0 ; $i < $n - 1 ; $i ++ ) { $val = $arr [ $i ] ^ $arr [ $i + 1 ]; $minXor = min ( $minXor $val ); } return $minXor ; } // Driver Code $arr = array ( 9 5 3 ); $n = count ( $arr ); echo minXOR ( $arr $n ); // This code is contributed by Smitha. ?>
JavaScript < script > // Function to find minimum XOR pair function minXOR ( arr n ) { // Sort given array arr . sort (); let minXor = Number . MAX_VALUE ; let val = 0 ; // calculate min xor of consecutive pairs for ( let i = 0 ; i < n - 1 ; i ++ ) { val = arr [ i ] ^ arr [ i + 1 ]; minXor = Math . min ( minXor val ); } return minXor ; } // Driver program let arr = [ 9 5 3 ]; let n = arr . length ; document . write ( minXOR ( arr n )); < /script>
산출
6
시간 복잡도: O(N*logN)
공간 복잡도: O(1)
더 나아가 효율적인 솔루션 정수가 저장하는 데 고정된 수의 비트를 사용한다는 가정하에 위의 문제를 O(n) 시간에 해결할 수 있습니다. 아이디어는 Trie 데이터 구조를 사용하는 것입니다.
연산:
- 빈 트라이를 만듭니다. trie의 모든 노드에는 0비트와 1비트에 대한 두 개의 하위 노드가 포함됩니다.
- min_xor 초기화 = INT_MAX arr[0]을 trie에 삽입
- 두 번째부터 시작하여 모든 배열 요소를 하나씩 순회합니다.
- 먼저 trie에서 최소 setbet 차이 값을 찾습니다.
- 해당 값의 최소 setbit diff로 현재 요소의 xor를 수행합니다.
- 필요한 경우 min_xor 값을 업데이트하세요.
- 현재 배열 요소를 트리에 삽입
- min_xor를 반환합니다.
아래는 위의 알고리즘을 구현한 것입니다.
C++ // C++ program to find minimum XOR value in an array. #include using namespace std ; #define INT_SIZE 32 // A Trie Node struct TrieNode { int value ; // used in leaf node TrieNode * Child [ 2 ]; }; // Utility function to create a new Trie node TrieNode * getNode () { TrieNode * newNode = new TrieNode ; newNode -> value = 0 ; newNode -> Child [ 0 ] = newNode -> Child [ 1 ] = NULL ; return newNode ; } // utility function insert new key in trie void insert ( TrieNode * root int key ) { TrieNode * temp = root ; // start from the most significant bit insert all // bit of key one-by-one into trie for ( int i = INT_SIZE - 1 ; i >= 0 ; i -- ) { // Find current bit in given prefix bool current_bit = ( key & ( 1 < < i )); // Add a new Node into trie if ( temp -> Child [ current_bit ] == NULL ) temp -> Child [ current_bit ] = getNode (); temp = temp -> Child [ current_bit ]; } // store value at leafNode temp -> value = key ; } // Returns minimum XOR value of an integer inserted // in Trie and given key. int minXORUtil ( TrieNode * root int key ) { TrieNode * temp = root ; for ( int i = INT_SIZE - 1 ; i >= 0 ; i -- ) { // Find current bit in given prefix bool current_bit = ( key & ( 1 < < i )); // Traversal Trie look for prefix that has // same bit if ( temp -> Child [ current_bit ] != NULL ) temp = temp -> Child [ current_bit ]; // if there is no same bit.then looking for // opposite bit else if ( temp -> Child [ 1 - current_bit ] != NULL ) temp = temp -> Child [ 1 - current_bit ]; } // return xor value of minimum bit difference value // so we get minimum xor value return key ^ temp -> value ; } // Returns minimum xor value of pair in arr[0..n-1] int minXOR ( int arr [] int n ) { int min_xor = INT_MAX ; // Initialize result // create a True and insert first element in it TrieNode * root = getNode (); insert ( root arr [ 0 ]); // Traverse all array element and find minimum xor // for every element for ( int i = 1 ; i < n ; i ++ ) { // Find minimum XOR value of current element with // previous elements inserted in Trie min_xor = min ( min_xor minXORUtil ( root arr [ i ])); // insert current array value into Trie insert ( root arr [ i ]); } return min_xor ; } // Driver code int main () { int arr [] = { 9 5 3 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < minXOR ( arr n ) < < endl ; return 0 ; }
Java // Java program to find minimum XOR value in an array. class GFG { static final int INT_SIZE = 32 ; // A Trie Node static class TrieNode { int value ; // used in leaf node TrieNode [] Child = new TrieNode [ 2 ] ; public TrieNode () { value = 0 ; Child [ 0 ] = null ; Child [ 1 ] = null ; } } static TrieNode root ; // utility function insert new key in trie static void insert ( int key ) { TrieNode temp = root ; // start from the most significant bit insert all // bit of key one-by-one into trie for ( int i = INT_SIZE - 1 ; i >= 0 ; i -- ) { // Find current bit in given prefix int current_bit = ( key & ( 1 < < i )) >= 1 ? 1 : 0 ; // Add a new Node into trie if ( temp != null && temp . Child [ current_bit ] == null ) temp . Child [ current_bit ] = new TrieNode (); temp = temp . Child [ current_bit ] ; } // store value at leafNode temp . value = key ; } // Returns minimum XOR value of an integer inserted // in Trie and given key. static int minXORUtil ( int key ) { TrieNode temp = root ; for ( int i = INT_SIZE - 1 ; i >= 0 ; i -- ) { // Find current bit in given prefix int current_bit = ( key & ( 1 < < i )) >= 1 ? 1 : 0 ; // Traversal Trie look for prefix that has // same bit if ( temp . Child [ current_bit ] != null ) temp = temp . Child [ current_bit ] ; // if there is no same bit.then looking for // opposite bit else if ( temp . Child [ 1 - current_bit ] != null ) temp = temp . Child [ 1 - current_bit ] ; } // return xor value of minimum bit difference value // so we get minimum xor value return key ^ temp . value ; } // Returns minimum xor value of pair in arr[0..n-1] static int minXOR ( int arr [] int n ) { int min_xor = Integer . MAX_VALUE ; // Initialize result // create a True and insert first element in it root = new TrieNode (); insert ( arr [ 0 ] ); // Traverse all array element and find minimum xor // for every element for ( int i = 1 ; i < n ; i ++ ) { // Find minimum XOR value of current element with // previous elements inserted in Trie min_xor = Math . min ( min_xor minXORUtil ( arr [ i ] )); // insert current array value into Trie insert ( arr [ i ] ); } return min_xor ; } // Driver code public static void main ( String args [] ) { int arr [] = { 9 5 3 }; int n = arr . length ; System . out . println ( minXOR ( arr n )); } } // This code is contributed by Sumit Ghosh
Python # class for the basic Trie Node class TrieNode : def __init__ ( self ): # Child array with 0 and 1 self . child = [ None ] * 2 # meant for the lead Node self . value = None class Trie : def __init__ ( self ): # initialise the root Node self . root = self . getNode () def getNode ( self ): # get a new Trie Node return TrieNode () # inserts a new element def insert ( self key ): temp = self . root # 32 bit valued binary digit for i in range ( 31 - 1 - 1 ): # finding the bit at ith position curr = ( key >> i ) & ( 1 ) # if the child is None create one if ( temp . child [ curr ] is None ): temp . child [ curr ] = self . getNode () temp = temp . child [ curr ] # add value to the leaf node temp . value = key # traverse the trie and xor with the most similar element def xorUtil ( self key ): temp = self . root # 32 bit valued binary digit for i in range ( 31 - 1 - 1 ): # finding the bit at ith position curr = ( key >> i ) & 1 # traverse for the same bit if ( temp . child [ curr ] is not None ): temp = temp . child [ curr ] # traverse if the same bit is not set in trie elif ( temp . child [ 1 - curr ] is not None ): temp = temp . child [ 1 - curr ] # return with the xor of the value return temp . value ^ key def minXor ( arr ): # set m to a large number m = 2 ** 30 # initialize Trie trie = Trie () # insert the first element trie . insert ( arr [ 0 ]) # for each element in the array for i in range ( 1 len ( arr )): # find the minimum xor value m = min ( m trie . xorUtil ( arr [ i ])) # insert the new element trie . insert ( arr [ i ]) return m # Driver Code if __name__ == '__main__' : sample = [ 9 5 3 ] print ( minXor ( sample )) #code contributed by Shushant Kumar
C# // Include namespace system using System ; // C# program to find minimum XOR value in an array. public class GFG { public const int INT_SIZE = 32 ; // A Trie Node public class TrieNode { public int value ; // used in leaf node public TrieNode [] Child = new TrieNode [ 2 ]; public TrieNode () { this . value = 0 ; this . Child [ 0 ] = null ; this . Child [ 1 ] = null ; } } public static TrieNode root ; // utility function insert new key in trie public static void insert ( int key ) { var temp = root ; // start from the most significant bit insert all // bit of key one-by-one into trie for ( int i = GFG . INT_SIZE - 1 ; i >= 0 ; i -- ) { // Find current bit in given prefix var current_bit = ( key & ( 1 < < i )) >= 1 ? 1 : 0 ; // Add a new Node into trie if ( temp != null && temp . Child [ current_bit ] == null ) { temp . Child [ current_bit ] = new TrieNode (); } temp = temp . Child [ current_bit ]; } // store value at leafNode temp . value = key ; } // Returns minimum XOR value of an integer inserted // in Trie and given key. public static int minXORUtil ( int key ) { var temp = root ; for ( int i = GFG . INT_SIZE - 1 ; i >= 0 ; i -- ) { // Find current bit in given prefix var current_bit = ( key & ( 1 < < i )) >= 1 ? 1 : 0 ; // Traversal Trie look for prefix that has // same bit if ( temp . Child [ current_bit ] != null ) { temp = temp . Child [ current_bit ]; } else if ( temp . Child [ 1 - current_bit ] != null ) { temp = temp . Child [ 1 - current_bit ]; } } // return xor value of minimum bit difference value // so we get minimum xor value return key ^ temp . value ; } // Returns minimum xor value of pair in arr[0..n-1] public static int minXOR ( int [] arr int n ) { var min_xor = int . MaxValue ; // Initialize result // create a True and insert first element in it root = new TrieNode (); GFG . insert ( arr [ 0 ]); // Traverse all array element and find minimum xor // for every element for ( int i = 1 ; i < n ; i ++ ) { // Find minimum XOR value of current element with // previous elements inserted in Trie min_xor = Math . Min ( min_xor GFG . minXORUtil ( arr [ i ])); // insert current array value into Trie GFG . insert ( arr [ i ]); } return min_xor ; } // Driver code public static void Main ( String [] args ) { int [] arr = { 9 5 3 }; var n = arr . Length ; Console . WriteLine ( GFG . minXOR ( arr n )); } } // This code is contributed by aadityaburujwale.
JavaScript class TrieNode { constructor () { this . child = new Array ( 2 ); this . value = null ; } } class Trie { constructor () { this . root = this . getNode (); } getNode () { return new TrieNode (); } insert ( key ) { let temp = this . root ; for ( let i = 31 ; i >= 0 ; i -- ) { let curr = ( key >> i ) & 1 ; if ( ! temp . child [ curr ]) temp . child [ curr ] = this . getNode (); temp = temp . child [ curr ]; } temp . value = key ; } xorUtil ( key ) { let temp = this . root ; for ( let i = 31 ; i >= 0 ; i -- ) { let curr = ( key >> i ) & 1 ; if ( temp . child [ curr ]) temp = temp . child [ curr ]; else if ( temp . child [ 1 - curr ]) temp = temp . child [ 1 - curr ]; } return temp . value ^ key ; } } function minXor ( arr ) { let m = 2 ** 30 ; let trie = new Trie (); trie . insert ( arr [ 0 ]); for ( let i = 1 ; i < arr . length ; i ++ ) { m = Math . min ( m trie . xorUtil ( arr [ i ])); trie . insert ( arr [ i ]); } return m ; } if ( typeof module !== 'undefined' ) { module . exports = { minXor : minXor }; } console . log ( minXor ([ 9 5 3 ])); // This code is contributed by akashish__
산출
6
시간 복잡도 O(n)
공간 복잡도: O(n*INT_SIZE)
퀴즈 만들기
