Maximum Array XOR [TC: O(32*(2N)); SC: O(1)]

max-array-xor.cpp

// Problem Link: https://practice.geeksforgeeks.org/problems/maximum-subset-xor/1/
// Good Explanation: https://www.geeksforgeeks.org/find-maximum-subset-xor-given-set/

int maxSubarrayXOR(int arr[], int n) {
  int maxEle = INT_MIN;
  for(int i = 0; i < n; ++i)
    maxEle = max(maxEle, arr[i]);
    
  int MSB = 0;
  for(int i = 31; i >= 0; --i)
    if((1 << i) & maxEle) { 
      MSB = i; break; 
    }
    
  int index = 0;
  for(int i = MSB; i >= 0; --i, ++index) {
    int maxIndex = index, maxElement = INT_MIN;
    for(int j = index; j < n; ++j)
      if((arr[j] & (1 << i)) && (arr[j] > maxElement))
        maxIndex = j, maxElement = arr[j];
        
    if(maxElement == INT_MIN) continue; // if there's no maxElement, there's no use going ahead.
        
    swap(arr[index], arr[maxIndex]); // since we don't want to affect the number in 'index' position
    maxIndex = index; // since now the position of maxElement is changed to 'index' in arr[]
        
    for(int j = 0; j < n; ++j)
      if(j != maxIndex && arr[j] & (1 << i))
        arr[j] ^= arr[maxIndex];
  }
    
  int res = 0;
  for(int i = 0; i < n; ++i) 
    res ^= arr[i];
    
  return res;
}

Problem Link
Good Explanation