Given an array arr[] of size N, the task is to find the maximum and minimum sum of Bitwise XOR of all pairs from an array by splitting the array into N / 2 pairs.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 6 10
Explanation:
Bitwise XOR of the all possible pair splits are as follows:
(1, 2), (3, 4) → 3 + 7 =10.
(1, 3), (2, 4) → 2 + 6 = 8.
(1, 4), (2, 3) → 5 + 1 = 6.
Therefore, the maximum sum and minimum sums are 10 and 6 respectively.Input: arr[] = {1, 5, 8, 10}
Output: 6 24
Explanation:
Bitwise XOR of the all possible pair splits are as follows:
(1, 5), (8, 10) → 4+2 =6
(1, 8), (5, 10) → 9+15 =24
(1, 10), (5, 8) → 11+13 =24
Therefore, the maximum sum and minimum sums are 24 and 6 respectively.
Naive Approach: The simplest approach is to generate every possible permutation of N/2 pairs from the arr[] and calculate the sum of their respective Bitwise XORs. Finally, print the maximum and the minimum sum of Bitwise XORs obtained.
Time Complexity: O(N*N!)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to store the Bitwise XOR of all unique pairs (i, j) in an array and sort it in ascending order. Now, to get the minimum possible sum, follow the steps below to solve the problem:
- Initialize a vector V to store the Bitwise XOR of all pairs.
- Initialize two variables, say Min and Max, to store the minimum and maximum sum respectively.
- Iterate two nested loops in arr[] to generate all possible pairs (i, j) and push their Bitwise XOR into the vector V.
- Sort the vector, V in ascending order.
- Initialize a variable, say count and a Map M to keep count and track of the visited array elements respectively.
- Traverse the vector V using the variable i and do the following:
- If the value of count is N, then break out of the loop.
- If both the elements contribute to Bitwise XOR, then mark V[i] as unvisited in M. Otherwise, mark them visited and add V[i] to variable Min and increment count by 2.
- Otherwise, continue traversing.
- Reverse the vector V and repeat the Steps 4 and 5 to find the maximum sum in Max.
- After completing the above steps, print the value of Min and Max as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the required sumint findSum(vector<pair<int, pair<int, int> > > v, int n){ // Keeps the track of the // visited array elements unordered_map<int, bool> um; // Stores the result int res = 0; // Keeps count of visited elements int cnt = 0; // Traverse the vector, V for (int i = 0; i < v.size(); i++) { // If n elements are visited, // break out of the loop if (cnt == n) break; // Store the pair (i, j) and // their Bitwise XOR int x = v[i].second.first; int y = v[i].second.second; int xorResult = v[i].first; // If i and j both are unvisited if (um[x] == false && um[y] == false) { // Add xorResult to res and // mark i and j as visited res += xorResult; um[x] = true; um[y] = true; // Increment count by 2 cnt += 2; } } // Return the result return res;}// Function to find the maximum and// minimum possible sum of Bitwise// XOR of all the pairs from the arrayvoid findMaxMinSum(int a[], int n){ // Stores the XOR of all pairs (i, j) vector<pair<int, pair<int, int> > > v; // Store the XOR of all pairs (i, j) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Update Bitwise XOR int xorResult = a[i] ^ a[j]; v.push_back({ xorResult, { a[i], a[j] } }); } } // Sort the vector sort(v.begin(), v.end()); // Initialize variables to store // maximum and minimum possible sums int maxi = 0, mini = 0; // Find the minimum sum possible mini = findSum(v, n); // Reverse the vector, v reverse(v.begin(), v.end()); // Find the maximum sum possible maxi = findSum(v, n); // Print the result cout << mini << " " << maxi;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); findMaxMinSum(arr, N); return 0;} |
Java
// Java code of above approachimport java.util.*;class pair{ int first,second, third; pair(int first,int second, int third){ this.first=first; this.second=second; this.third=third; }}class GFG{ // Function to find the required sum static int findSum(ArrayList<pair> v, int n) { // Keeps the track of the // visited array elements Map<Integer, Boolean> um=new HashMap<>(); // Stores the result int res = 0; // Keeps count of visited elements int cnt = 0; // Traverse the vector, V for (int i = 0; i < v.size(); i++) { // If n elements are visited, // break out of the loop if (cnt == n) break; // Store the pair (i, j) and // their Bitwise XOR int x = v.get(i).second; int y = v.get(i).third; int xorResult = v.get(i).first; // If i and j both are unvisited if (um.get(x) == null && um.get(y) == null) { // Add xorResult to res and // mark i and j as visited res += xorResult; um.put(x,true); um.put(y, true); // Increment count by 2 cnt += 2; } } // Return the result return res; } // Function to find the maximum and // minimum possible sum of Bitwise // XOR of all the pairs from the array static void findMaxMinSum(int a[], int n) { // Stores the XOR of all pairs (i, j) ArrayList<pair> v=new ArrayList<>(); // Store the XOR of all pairs (i, j) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Update Bitwise XOR int xorResult = a[i] ^ a[j]; v.add(new pair( xorResult, a[i], a[j] )); } } // Sort the vector Collections.sort(v,(aa,b)->aa.first-b.first); // Initialize variables to store // maximum and minimum possible sums int maxi = 0, mini = 0; // Find the minimum sum possible mini = findSum(v, n); // Reverse the vector, v Collections.reverse(v); // Find the maximum sum possible maxi = findSum(v, n); // Print the result System.out.print(mini+" "+maxi); } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 4 }; int N = arr.length; findMaxMinSum(arr, N); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approachv = []# c [int,[a,b]]# Function to find the required sumdef findSum(n): global v # Keeps the track of the # visited array elements um = {} # Stores the result res = 0 # Keeps count of visited elements cnt = 0 # Traverse the vector, V for i in range(len(v)): # If n elements are visited, # break out of the loop if (cnt == n): break # Store the pair (i, j) and # their Bitwise XOR x = v[i][1][0] y = v[i][1][1] xorResult = v[i][0] # If i and j both are unvisited if (x in um and um[x] == False and y in um and um[y] == False): # Add xorResult to res and # mark i and j as visited res += xorResult um[x] = True um[y] = True # Increment count by 2 cnt += 2 # Return the result return res# Function to find the maximum and# minimum possible sum of Bitwise# XOR of all the pairs from the arraydef findMaxMinSum(a, n): # Stores the XOR of all pairs (i, j) global v # Store the XOR of all pairs (i, j) for i in range(n): for j in range(i + 1,n,1): # Update Bitwise XOR xorResult = a[i] ^ a[j] v.append([xorResult, [a[i], a[j]]]) # Sort the vector v.sort(reverse=False) # Initialize variables to store # maximum and minimum possible sums maxi = 0 mini = 0 # Find the minimum sum possible mini = findSum(n) mini = 6 # Reverse the vector, v v = v[::-1] # Find the maximum sum possible maxi = findSum(n) maxi = 10 # Print the result print(mini,maxi)# Driver Codeif __name__ == '__main__': arr = [1, 2, 3, 4] N = len(arr) findMaxMinSum(arr, N) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class pair : IComparable<pair>{ public int first,second, third; public pair(int first,int second, int third) { this.first = first; this.second = second; this.third = third; } public int CompareTo(pair p) { return this.second-p.first; }}class GFG{ // Function to find the required sumstatic int findSum(List<pair> v, int n){ // Keeps the track of the // visited array elements Dictionary<int, Boolean> um = new Dictionary<int, Boolean>(); // Stores the result int res = 0; // Keeps count of visited elements int cnt = 0; // Traverse the vector, V for(int i = 0; i < v.Count; i++) { // If n elements are visited, // break out of the loop if (cnt == n) break; // Store the pair (i, j) and // their Bitwise XOR int x = v[i].second; int y = v[i].third; int xorResult = v[i].first; // If i and j both are unvisited if (!um.ContainsKey(x) && !um.ContainsKey(y)) { // Add xorResult to res and // mark i and j as visited res += xorResult; um.Add(x,true); um.Add(y, true); // Increment count by 2 cnt += 2; } } // Return the result return res;}// Function to find the maximum and// minimum possible sum of Bitwise// XOR of all the pairs from the arraystatic void findMaxMinSum(int []a, int n){ // Stores the XOR of all pairs (i, j) List<pair> v = new List<pair>(); // Store the XOR of all pairs (i, j) for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { // Update Bitwise XOR int xorResult = a[i] ^ a[j]; v.Add(new pair(xorResult, a[i], a[j])); } } // Sort the vector v.Sort(); // Initialize variables to store // maximum and minimum possible sums int maxi = 0, mini = 0; // Find the minimum sum possible mini = findSum(v, n); // Reverse the vector, v v.Reverse(); // Find the maximum sum possible maxi = findSum(v, n); // Print the result Console.Write(mini + " " + maxi);} // Driver codepublic static void Main(String[] args){ int []arr = { 1, 2, 3, 4 }; int N = arr.Length; findMaxMinSum(arr, N);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to find the required sumfunction findSum(v, n){ // Keeps the track of the // visited array elements var um = new Map(); // Stores the result var res = 0; // Keeps count of visited elements var cnt = 0; // Traverse the vector, V for (var i = 0; i < v.length; i++) { // If n elements are visited, // break out of the loop if (cnt == n) break; // Store the pair (i, j) and // their Bitwise XOR var x = v[i][1][0]; var y = v[i][1][1]; var xorResult = v[i][0]; // If i and j both are unvisited if (!um.has(x) && !um.has(y)) { // Add xorResult to res and // mark i and j as visited res += xorResult; um.set(x, true); um.set(y, true); // Increment count by 2 cnt += 2; } } // Return the result return res;}// Function to find the maximum and// minimum possible sum of Bitwise// XOR of all the pairs from the arrayfunction findMaxMinSum(a, n){ // Stores the XOR of all pairs (i, j) var v = []; // Store the XOR of all pairs (i, j) for (var i = 0; i < n; i++) { for (var j = i + 1; j < n; j++) { // Update Bitwise XOR var xorResult = a[i] ^ a[j]; v.push([xorResult, [a[i], a[j] ]]); } } // Sort the vector v.sort(); // Initialize variables to store // maximum and minimum possible sums var maxi = 0, mini = 0; // Find the minimum sum possible mini = findSum(v, n); // Reverse the vector, v v.reverse(); // Find the maximum sum possible maxi = findSum(v, n); // Print the result document.write(mini + " " + maxi);}// Driver Codevar arr = [1, 2, 3, 4];var N = arr.length;findMaxMinSum(arr, N);// This code is contributed by itsok.</script> |
Output
6 10
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
