Given an array arr[] of N integers and an integer K. The task is to find the maximum xor subset of size K of the given array.
Examples:
Input: arr[] = {2, 5, 4, 1, 3, 7, 6, 8}, K = 3
Output: 15
We obtain 15 by selecting 2, 5, 8
Input: arr[] = {3, 4, 7, 7, 9}, K = 3
Output: 14
Naive approach: Iterate over all subsets of size K of the array and find maximum xor among them.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum xor for a// subset of size k from the given arrayint Max_Xor(int arr[], int n, int k){ // Initialize result int maxXor = INT_MIN; // Traverse all subsets of the array for (int i = 0; i < (1 << n); i++) { // __builtin_popcount() returns the number // of sets bits in an integer if (__builtin_popcount(i) == k) { // Initialize current xor as 0 int cur_xor = 0; for (int j = 0; j < n; j++) { // If jth bit is set in i then include // jth element in the current xor if (i & (1 << j)) cur_xor = cur_xor ^ arr[j]; } // Update maximum xor so far maxXor = max(maxXor, cur_xor); } } return maxXor;}// Driver codeint main(){ int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 }; int n = sizeof(arr) / sizeof(int); int k = 3; cout << Max_Xor(arr, n, k); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function to return the maximum xor for a// subset of size k from the given arraystatic int Max_Xor(int arr[], int n, int k){ // Initialize result int maxXor = Integer.MIN_VALUE; // Traverse all subsets of the array for (int i = 0; i < (1 << n); i++) { // __builtin_popcount() returns the number // of sets bits in an integer if (Integer.bitCount(i) == k) { // Initialize current xor as 0 int cur_xor = 0; for (int j = 0; j < n; j++) { // If jth bit is set in i then include // jth element in the current xor if ((i & (1 << j)) == 0) cur_xor = cur_xor ^ arr[j]; } // Update maximum xor so far maxXor = Math.max(maxXor, cur_xor); } } return maxXor;}// Driver codepublic static void main(String[] args){ int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 }; int n = arr.length; int k = 3; System.out.println(Max_Xor(arr, n, k));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python implementation of the approachMAX = 10000MAX_ELEMENT = 50dp =[[[-1 for i in range(MAX)] for j in range(MAX_ELEMENT)] for k in range(MAX_ELEMENT)]# Function to return the maximum xor for a# subset of size j from the given arraydef Max_Xor(arr, i, j, mask, n): if (i >= n): # If the subset is complete then return # the xor value of the selected elements if (j == 0): return mask else: return 0 # Return if already calculated for some # mask and j at the i'th index if (dp[i][j][mask] != -1): return dp[i][j][mask] # Initialize answer to 0 ans = 0 # If we can still include elements in our subset # include the i'th element if (j > 0): ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n) # Exclude the i'th element # ans store the max of both operations ans = max(ans, Max_Xor(arr, i + 1, j, mask, n)) dp[i][j][mask] = ans return ans# Driver codearr = [2, 5, 4, 1, 3, 7, 6, 8]n = len(arr)k = 3print(Max_Xor(arr, 0, k, 0, n))# This code is contributed by shubhamsingh10 |
C#
// C# implementation of the approachusing System; class GFG {// Function to return the maximum xor for a// subset of size k from the given arraystatic int Max_Xor(int []arr, int n, int k){ // Initialize result int maxXor = int.MinValue; // Traverse all subsets of the array for (int i = 0; i < (1 << n); i++) { // __builtin_popcount() returns the number // of sets bits in an integer if (bitCount(i) == k) { // Initialize current xor as 0 int cur_xor = 0; for (int j = 0; j < n; j++) { // If jth bit is set in i then include // jth element in the current xor if ((i & (1 << j)) == 0) cur_xor = cur_xor ^ arr[j]; } // Update maximum xor so far maxXor = Math.Max(maxXor, cur_xor); } } return maxXor;}static int bitCount(long x){ int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;} // Driver codepublic static void Main(String[] args){ int []arr = { 2, 5, 4, 1, 3, 7, 6, 8 }; int n = arr.Length; int k = 3; Console.WriteLine(Max_Xor(arr, n, k));}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Function to return the maximum xor for a// subset of size k from the given arrayfunction Max_Xor(arr, n, k){ // Initialize result let maxXor = Number.MIN_VALUE; // Traverse all subsets of the array for (let i = 0; i < (1 << n); i++) { // bitCount() returns the number // of sets bits in an integer if (bitCount(i) == k) { // Initialize current xor as 0 let cur_xor = 0; for (let j = 0; j < n; j++) { // If jth bit is set in i then include // jth element in the current xor if (i & (1 << j)) cur_xor = cur_xor ^ arr[j]; } // Update maximum xor so far maxXor = Math.max(maxXor, cur_xor); } } return maxXor;}function bitCount(x){ let setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits;} // Driver code let arr = [ 2, 5, 4, 1, 3, 7, 6, 8 ]; let n = arr.length; let k = 3; document.write(Max_Xor(arr, n, k));</script> |
Output
15
Time Complexity: O(n*2n)
Auxiliary Space: O(1)
Efficient approach: The problem can be solved using dynamic programming. Create a dp table dp[i][j][mask] which stores the maximum xor possible at the ith index (with or without including it) and j denotes the number of remaining elements we can include in our subset of K elements. Mask is the xor of all the elements selected till the ith index.
Note: This approach will only work for smaller arrays due to space requirements for the dp array.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define MAX 10000#define MAX_ELEMENT 50int dp[MAX_ELEMENT][MAX_ELEMENT][MAX];// Function to return the maximum xor for a// subset of size j from the given arrayint Max_Xor(int arr[], int i, int j, int mask, int n){ if (i >= n) { // If the subset is complete then return // the xor value of the selected elements if (j == 0) return mask; else return 0; } // Return if already calculated for some // mask and j at the i'th index if (dp[i][j][mask] != -1) return dp[i][j][mask]; // Initialize answer to 0 int ans = 0; // If we can still include elements in our subset // include the i'th element if (j > 0) ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n); // Exclude the i'th element // ans store the max of both operations ans = max(ans, Max_Xor(arr, i + 1, j, mask, n)); return dp[i][j][mask] = ans;}// Driver codeint main(){ int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 }; int n = sizeof(arr) / sizeof(int); int k = 3; memset(dp, -1, sizeof(dp)); cout << Max_Xor(arr, 0, k, 0, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int MAX = 10000;static int MAX_ELEMENT = 50;static int [][][] dp = new int[MAX_ELEMENT][MAX_ELEMENT][MAX];// Function to return the maximum xor for a// subset of size j from the given arraystatic int Max_Xor(int arr[], int i, int j, int mask, int n){ if (i >= n) { // If the subset is complete then return // the xor value of the selected elements if (j == 0) return mask; else return 0; } // Return if already calculated for some // mask and j at the i'th index if (dp[i][j][mask] != -1) return dp[i][j][mask]; // Initialize answer to 0 int ans = 0; // If we can still include elements in our subset // include the i'th element if (j > 0) ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n); // Exclude the i'th element // ans store the max of both operations ans = Math.max(ans, Max_Xor(arr, i + 1, j, mask, n)); return dp[i][j][mask] = ans;}// Driver codepublic static void main(String[] args){ int arr[] = { 2, 5, 4, 1, 3, 7, 6, 8 }; int n = arr.length; int k = 3; for(int i = 0; i < MAX_ELEMENT; i++) { for(int j = 0; j < MAX_ELEMENT; j++) { for(int l = 0; l < MAX; l++) dp[i][j][l] = -1; } } System.out.println(Max_Xor(arr, 0, k, 0, n));}}// This code is contributed by Princi Singh |
Python3
# Python implementation of the approachMAX = 10000MAX_ELEMENT = 50dp =[[[-1 for i in range(MAX)] for j in range(MAX_ELEMENT)] for k in range(MAX_ELEMENT)]# Function to return the maximum xor for a# subset of size j from the given arraydef Max_Xor(arr, i, j, mask, n): if (i >= n): # If the subset is complete then return # the xor value of the selected elements if (j == 0): return mask else: return 0 # Return if already calculated for some # mask and j at the i'th index if (dp[i][j][mask] != -1): return dp[i][j][mask] # Initialize answer to 0 ans = 0 # If we can still include elements in our subset # include the i'th element if (j > 0): ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n) # Exclude the i'th element # ans store the max of both operations ans = max(ans, Max_Xor(arr, i + 1, j, mask, n)) dp[i][j][mask] = ans return ans# Driver codearr = [2, 5, 4, 1, 3, 7, 6, 8]n = len(arr)k = 3print(Max_Xor(arr, 0, k, 0, n))# This code is contributed by shubhamsingh10 |
C#
// C# implementation of the approachusing System;class GFG{ static int MAX = 10000; static int MAX_ELEMENT = 50; static int [,,] dp = new int[MAX_ELEMENT, MAX_ELEMENT, MAX]; // Function to return the maximum xor for a // subset of size j from the given array static int Max_Xor(int[] arr, int i, int j, int mask, int n) { if (i >= n) { // If the subset is complete then return // the xor value of the selected elements if (j == 0) return mask; else return 0; } // Return if already calculated for some // mask and j at the i'th index if (dp[i,j,mask] != -1) return dp[i,j,mask]; // Initialize answer to 0 int ans = 0; // If we can still include elements in our subset // include the i'th element if (j > 0) ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n); // Exclude the i'th element // ans store the max of both operations ans = Math.Max(ans, Max_Xor(arr, i + 1, j, mask, n)); return dp[i,j,mask] = ans; } // Driver code public static void Main () { int[] arr = { 2, 5, 4, 1, 3, 7, 6, 8 }; int n = arr.Length; int k = 3; for(int i = 0; i < MAX_ELEMENT; i++) { for(int j = 0; j < MAX_ELEMENT; j++) { for(int l = 0; l < MAX; l++) dp[i,j,l] = -1; } } Console.WriteLine(Max_Xor(arr, 0, k, 0, n)); }}// This code is contributed by target_2. |
Javascript
//JS implementation of the approachconst MAX = 10000;const MAX_ELEMENT = 50;//declaring and building dpvar dp = [];for (var i = 0; i < MAX_ELEMENT; i++){ dp[i] = []; for (var j = 0; j < MAX_ELEMENT; j++) { dp[i][j] = []; for (var k = 0; k < MAX_ELEMENT; k++) { dp[i][j][k] = -1; } }}// Function to return the maximum xor for a// subset of size j from the given arrayfunction Max_Xor(arr, i, j, mask, n){ if (i >= n) { // If the subset is complete then return // the xor value of the selected elements if (j == 0) return mask; else return 0; } // Return if already calculated for some // mask and j at the i'th index if (dp[i][j][mask] != -1) return dp[i][j][mask]; // Initialize answer to 0 var ans = 0; // If we can still include elements in our subset // include the i'th element if (j > 0) ans = Max_Xor(arr, i + 1, j - 1, mask ^ arr[i], n); // Exclude the i'th element // ans store the max of both operations ans = Math.max(ans, Max_Xor(arr, i + 1, j, mask, n)); dp[i][j][mask] = ans; return ans;}// Driver codevar arr = [2, 5, 4, 1, 3, 7, 6, 8];var n = arr.length;var k = 3;console.log(Max_Xor(arr, 0, k, 0, n));// This code is contributed by phasing17 |
Output
15
Time Complexity: O(n*n)
Auxiliary Space: O(MAX*MAX_ELEMENT2) where MAX and MAX_ELEMENT are defined constants.
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!
