Given an array arr[] of N integers, where N is an even number. The task is to divide the given N integers into two equal subsets such that the sum of Bitwise XOR of all elements of two subsets is maximum.
Examples:
Input: N= 4, arr[] = {1, 2, 3, 4}
Output: 10
Explanation:
There are 3 ways possible:
(1, 2)(3, 4) = (1^2)+(3^4) = 10
(1, 3)(2, 4) = (1^3)+(2^3) = 8
(1, 4)(2, 3) = (1^4)+(2^3) = 6
Hence, the maximum sum = 10Input: N= 6, arr[] = {4, 5, 3, 2, 5, 6}
Output: 17
Naive Approach: The idea is to check every possible distribution of N/2 pairs. Print the Bitwise XOR of the sum of all elements of two subsets which is maximum.
Time Complexity: O(N*N!)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming Using Bit Masking. Follow the below steps to solve the problem:
- Initially, the bitmask is 0, if the bit is set then the pair is already picked.
- Iterate through all the possible pairs and check if it is possible to pick a pair i.e., the bits of i and j are not set in the mask:
- If it is possible to take the pair then find the Bitwise XOR sum for the current pair and check for the next pair recursively.
- Else check for the next pair of elements.
- Keep updating the maximum XOR pair sum in the above step for each recursive call.
- Print the maximum value of all possible pairs stored in dp[mask].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function that finds the maximum// Bitwise XOR sum of the two subsetint xorSum(int a[], int n, int mask, int dp[]){ // Check if the current state is // already computed if (dp[mask] != -1) { return dp[mask]; } // Initialize answer to minimum value int max_value = 0; // Iterate through all possible pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check whether ith bit and // jth bit of mask is not // set then pick the pair if (i != j && (mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) { // For all possible pairs // find maximum value pick // current a[i], a[j] and // set i, j th bits in mask max_value = max(max_value, (a[i] ^ a[j]) + xorSum(a, n, (mask | (1 << i) | (1 << j)), dp)); } } } // Store the maximum value // and return the answer return dp[mask] = max_value;}// Driver Codeint main(){ int n = 4; // Given array arr[] int arr[] = { 1, 2, 3, 4 }; // Declare Initialize the dp states int dp[(1 << n) + 5]; memset(dp, -1, sizeof(dp)); // Function Call cout << (xorSum(arr, n, 0, dp));}// This code is contributed by Rohit_ranjan |
Java
// Java program for the above approachimport java.util.*;import java.io.*;public class GFG { // Function that finds the maximum // Bitwise XOR sum of the two subset public static int xorSum(int a[], int n, int mask, int[] dp) { // Check if the current state is // already computed if (dp[mask] != -1) { return dp[mask]; } // Initialize answer to minimum value int max_value = 0; // Iterate through all possible pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check whether ith bit and // jth bit of mask is not // set then pick the pair if (i != j && (mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) { // For all possible pairs // find maximum value pick // current a[i], a[j] and // set i, j th bits in mask max_value = Math.max( max_value, (a[i] ^ a[j]) + xorSum(a, n, (mask | (1 << i) | (1 << j)), dp)); } } } // Store the maximum value // and return the answer return dp[mask] = max_value; } // Driver Code public static void main(String args[]) { int n = 4; // Given array arr[] int arr[] = { 1, 2, 3, 4 }; // Declare Initialize the dp states int dp[] = new int[(1 << n) + 5]; Arrays.fill(dp, -1); // Function Call System.out.println(xorSum(arr, n, 0, dp)); }} |
Python3
# Python3 program to implement# the above approach# Function that finds the maximum # Bitwise XOR sum of the two subsetdef xorSum(a, n, mask, dp): # Check if the current state is # already computed if(dp[mask] != -1): return dp[mask] # Initialize answer to minimum value max_value = 0 # Iterate through all possible pairs for i in range(n): for j in range(i + 1, n): # Check whether ith bit and # jth bit of mask is not # set then pick the pair if(i != j and (mask & (1 << i)) == 0 and (mask & (1 << j)) == 0): # For all possible pairs # find maximum value pick # current a[i], a[j] and # set i, j th bits in mask max_value = max(max_value, (a[i] ^ a[j]) + xorSum(a, n, (mask | (1 << i) | (1 << j)), dp)) # Store the maximum value # and return the answer dp[mask] = max_value return dp[mask]# Driver Coden = 4# Given array arr[]arr = [ 1, 2, 3, 4 ]# Declare Initialize the dp statesdp = [-1] * ((1 << n) + 5)# Function callprint(xorSum(arr, n, 0, dp))# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{// Function that finds the maximum// Bitwise XOR sum of the two subsetpublic static int xorSum(int []a, int n, int mask, int[] dp){ // Check if the current state is // already computed if (dp[mask] != -1) { return dp[mask]; } // Initialize answer to minimum value int max_value = 0; // Iterate through all possible pairs for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { // Check whether ith bit and // jth bit of mask is not // set then pick the pair if (i != j && (mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) { // For all possible pairs // find maximum value pick // current a[i], a[j] and // set i, j th bits in mask max_value = Math.Max( max_value, (a[i] ^ a[j]) + xorSum(a, n, (mask | (1 << i) | (1 << j)), dp)); } } } // Store the maximum value // and return the answer return dp[mask] = max_value;}// Driver Codepublic static void Main(String []args){ int n = 4; // Given array []arr int []arr = { 1, 2, 3, 4 }; // Declare Initialize the dp states int []dp = new int[(1 << n) + 5]; for(int i = 0; i < dp.Length; i++) dp[i] = -1; // Function call Console.WriteLine(xorSum(arr, n, 0, dp));}}// This code is contributed by amal kumar choubey |
Javascript
<script>// JavaScript program for the above approach// Function that finds the maximum// Bitwise XOR sum of the two subsetfunction xorSum(a, n, mask, dp){ // Check if the current state is // already computed if (dp[mask] != -1) { return dp[mask]; } // Initialize answer to minimum value var max_value = 0; // Iterate through all possible pairs for (var i = 0; i < n; i++) { for (var j = i + 1; j < n; j++) { // Check whether ith bit and // jth bit of mask is not // set then pick the pair if (i != j && (mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) { // For all possible pairs // find maximum value pick // current a[i], a[j] and // set i, j th bits in mask max_value = Math.max(max_value, (a[i] ^ a[j]) + xorSum(a, n, (mask | (1 << i) | (1 << j)), dp)); } } } // Store the maximum value // and return the answer return dp[mask] = max_value;}// Driver Codevar n = 4;// Given array arr[]var arr = [1, 2, 3, 4];// Declare Initialize the dp statesvar dp = Array((1 << n) + 5).fill(-1);// Function Calldocument.write(xorSum(arr, n, 0, dp));</script> |
Output
10
Time Complexity: O(N2*2N), where N is the size of the given array
Auxiliary Space: O(N)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively
- Return the final solution
Implementation:
C++
// C++ program for above approach#include<bits/stdc++.h>using namespace std;// Function that finds the maximum// Bitwise XOR sum of the two subsetint xorSum(int a[], int n){ // Declare dp table and initialize // with all elements as 0 int dp[1 << n]; memset(dp, 0, sizeof(dp)); // Fill the dp table for (int mask = 0; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check whether ith bit and // jth bit of mask is not set // then pick the pair if ((mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) { // Update dp table with // maximum value pick // current a[i], a[j] and // set i, j th bits in mask dp[mask | (1 << i) | (1 << j)] = max(dp[mask | (1 << i) | (1 << j)], dp[mask] + (a[i] ^ a[j])); } } } } // Return the maximum value return dp[(1 << n) - 1];}// Driver Codeint main(){ int n = 4; // Given array arr[] int arr[] = { 1, 2, 3, 4 }; // Function Call cout << (xorSum(arr, n));}// this code is contributed by bhardwajji |
Java
// java code addition import java.io.*;import java.util.*;public class Main { // Function that finds the maximum // Bitwise XOR sum of the two subset static int xorSum(int a[], int n) { // Declare dp table and initialize // with all elements as 0 int dp[] = new int[1 << n]; Arrays.fill(dp, 0); // Fill the dp table for (int mask = 0; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check whether ith bit and // jth bit of mask is not set // then pick the pair if ((mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) { // Update dp table with // maximum value pick // current a[i], a[j] and // set i, j th bits in mask dp[mask | (1 << i) | (1 << j)] = Math.max(dp[mask | (1 << i) | (1 << j)], dp[mask] + (a[i] ^ a[j])); } } } } // Return the maximum value return dp[(1 << n) - 1]; } // Driver Code public static void main(String[] args) { int n = 4; // Given array arr[] int arr[] = { 1, 2, 3, 4 }; // Function Call System.out.println(xorSum(arr, n)); }}// The code is contributed by Nidhi goel. |
Python
# Python program for above approachimport math# Function that finds the maximum# Bitwise XOR sum of the two subsetdef xorSum(a, n): # Declare dp table and initialize # with all elements as 0 dp = [0]*(1 << n) # Fill the dp table for mask in range(1 << n): for i in range(n): for j in range(i+1, n): # Check whether ith bit and # jth bit of mask is not set # then pick the pair if (mask & (1 << i)) == 0 and (mask & (1 << j)) == 0: # Update dp table with # maximum value pick # current a[i], a[j] and # set i, j th bits in mask dp[mask | (1 << i) | (1 << j)] = max( dp[mask | (1 << i) | (1 << j)], dp[mask] + (a[i] ^ a[j])) # Return the maximum value return dp[(1 << n) - 1]# Driver Codeif __name__ == '__main__': n = 4 # Given array arr[] arr = [1, 2, 3, 4] # Function Call print(xorSum(arr, n))# This code is contributed by user_dtewbxkn77n |
C#
using System;public class Program { // Function that finds the maximum // Bitwise XOR sum of the two subset static int xorSum(int[] a, int n) { // Declare dp table and initialize // with all elements as 0 int[] dp = new int[1 << n]; Array.Fill(dp, 0); // Fill the dp table for (int mask = 0; mask < (1 << n); mask++) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check whether ith bit and // jth bit of mask is not set // then pick the pair if ((mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) { // Update dp table with // maximum value pick // current a[i], a[j] and // set i, j th bits in mask dp[mask | (1 << i) | (1 << j)] = Math.Max(dp[mask | (1 << i) | (1 << j)], dp[mask] + (a[i] ^ a[j])); } } } } // Return the maximum value return dp[(1 << n) - 1]; } // Driver Code static void Main(string[] args) { int n = 4; // Given array arr[] int[] arr = { 1, 2, 3, 4 }; // Function Call Console.WriteLine(xorSum(arr, n)); }} |
Javascript
// JavaScript code equivalent of the Java code abovefunction xorSum(a, n) {// Declare dp table and initialize// with all elements as 0let dp = new Array(1 << n).fill(0);// Fill the dp tablefor (let mask = 0; mask < (1 << n); mask++) {for (let i = 0; i < n; i++) {for (let j = i + 1; j < n; j++) {// Check whether ith bit and jth bit of mask is not set// then pick the pairif ((mask & (1 << i)) == 0 && (mask & (1 << j)) == 0) {// Update dp table with// maximum value pick// current a[i], a[j] and// set i, j th bits in maskdp[mask | (1 << i) | (1 << j)] =Math.max(dp[mask | (1 << i) | (1 << j)],dp[mask] + (a[i] ^ a[j]));}}}}// Return the maximum valuereturn dp[(1 << n) - 1];}// Driver Codelet n = 4;// Given array arr[]let arr = [1, 2, 3, 4];// Function Callconsole.log(xorSum(arr, n)); |
Output
10
Time Complexity: O(N2*2N)
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!
