Maximum and minimum sum of Bitwise XOR of pairs from an array | C ++ program for the above approach ; Function to find the required sum ; Keeps the track of the visited array elements ; Stores the result ; Keeps count of visited elements ; Traverse the vector , V ; If n elements are visited , break out of the loop ; Store the pair ( i , j ) and their Bitwise XOR ; If i and j both are unvisited ; Add xorResult to res and mark i and j as visited ; Increment count by 2 ; Return the result ; Function to find the maximum and minimum possible sum of Bitwise XOR of all the pairs from the array ; Stores the XOR of all pairs ( i , j ) ; Store the XOR of all pairs ( i , j ) ; Update Bitwise XOR ; Sort the vector ; Initialize variables to store maximum and minimum possible sums ; Find the minimum sum possible ; Reverse the vector , v ; Find the maximum sum possible ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSum ( vector < pair < int , pair < int , int > > > v , int n ) { unordered_map < int , bool > um ; int res = 0 ; int cnt = 0 ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { if ( cnt == n ) break ; int x = v [ i ] . second . first ; int y = v [ i ] . second . second ; int xorResult = v [ i ] . first ; if ( um [ x ] == false && um [ y ] == false ) { res += xorResult ; um [ x ] = true ; um [ y ] = true ; cnt += 2 ; } } return res ; } void findMaxMinSum ( int a [ ] , int n ) { vector < pair < int , pair < int , int > > > v ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int xorResult = a [ i ] ^ a [ j ] ; v . push_back ( { xorResult , { a [ i ] , a [ j ] } } ) ; } } sort ( v . begin ( ) , v . end ( ) ) ; int maxi = 0 , mini = 0 ; mini = findSum ( v , n ) ; reverse ( v . begin ( ) , v . end ( ) ) ; maxi = findSum ( v , n ) ; cout << mini << " ▁ " << maxi ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findMaxMinSum ( arr , N ) ; return 0 ; }