Find the maximum subset XOR of a given set - GeeksforGeeks
Given an set of positive integers. find the maximum XOR subset value in the given set. Expected time complexity O(n).
Examples:
Input: set[] = {2, 4, 5} Output: 7 The subset {2, 5} has maximum XOR value Input: set[] = {9, 8, 5} Output: 13 The subset {8, 5} has maximum XOR value Input: set[] = {8, 1, 2, 12, 7, 6} Output: 15 The subset {1, 2, 12} has maximum XOR value Input: set[] = {4, 6} Output: 6 The subset {6} has maximum XOR value Note that this problem is different from the maximum subarray XOR. Here we need to find subset instead of subarray.
We strongly recommend you to minimize your browser and try this yourself first.
A Simple Solution is to generate all possible subsets of given set, find XOR of every subset and return the subset with maximum XOR.
Below is an Efficient Algorithm that works in O(n) time.
The idea is based on below facts:
- Number of bits to represent all elements is fixed which is 32 bits for integer in most of the compilers.
- If maximum element has Most Significant Bit MSB at position i, then result is at least 2i
1. Initialize index of chosen elements as 0. Let this index be 'index' 2. Traverse through all bits starting from most significant bit. Let i be the current bit. ......(a) Find the maximum element with i'th bit set. If there is no element with i'th bit set, continue to smaller bit. ......(b) Let the element with i'th bit set be maxEle and index of this element be maxInd. Place maxEle at 'index' and (by swapping set[index] and set[maxInd]) ......(c) Do XOR of maxEle with all numbers having i'th bit as set. ......(d) Increment index 3. Return XOR of all elements in set[]. Note that set[] is modified in step 2.c.
Read full article from Find the maximum subset XOR of a given set - GeeksforGeeks
No comments:
Post a Comment