- Arrays, Bit Magic, Bitwise-OR, Bitwise-XOR, Greedy, Mathematical, partition, Recursion, subarray

Split an array into subarrays with maximum Bitwise XOR of their respective Bitwise OR values

Split an array into subarrays with maximum Bitwise XOR of their respective Bitwise OR valuesGiven an array arr[] consisting of N integers, the task is to find the maximum Bitwise XOR of Bitwise OR of every subarray after splitting the array into subarrays(possible zero subarrays).Examples:Input: arr[] = {1, 5, 7}, N = 3Output: 7Explanation:The given array can be expressed as the 1 subarray i.e., {1, 5, 7}.The Bitwise XOR of the Bitwise OR of the formed subarray is 7, which is the maximum possible value.Input: arr[] = {1, 2}, N = 2Output: 3Naive Approach: The simplest approach to solve the given above problem is to generate all possible combinations of breaking of subarrays using recursion and at each recursive call, find the maximum value of Bitwise XOR of Bitwise OR of all possible formed subarray and print it.Below is the implementation of the above approach:C++#include using namespace std;int maxXORUtil(int arr[], int N,               int xrr, int orr){        if (N == 0)        return xrr ^ orr;                int x = maxXORUtil(arr, N – 1,                       xrr ^ orr,                       arr[N – 1]);                int y = maxXORUtil(arr, N – 1,                       xrr, orr | arr[N – 1]);            return max(x, y);}int maximumXOR(int arr[], int N){        return maxXORUtil(arr, N, 0, 0);}int main(){    int arr[] = { 1, 5, 7 };    int N = sizeof(arr) / sizeof(arr[0]);    cout