Given 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 = 3
Output: 7
Explanation:
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 = 2
Output: 3
Naive 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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to find all the// possible breaking of arrays into// subarrays and find the maximum// Bitwise XORint maxXORUtil(int arr[], int N, int xrr, int orr){ // If the value of N is 0 if (N == 0) return xrr ^ orr; // Stores the result if the new // group is formed with the first // element as arr[i] int x = maxXORUtil(arr, N - 1, xrr ^ orr, arr[N - 1]); // Stores if the result if the // arr[i] is included in the // last group int y = maxXORUtil(arr, N - 1, xrr, orr | arr[N - 1]); // Returns the maximum of // x and y return max(x, y);}// Function to find the maximum possible// Bitwise XOR of all possible values of// the array after breaking the arrays// into subarraysint maximumXOR(int arr[], int N){ // Return the result return maxXORUtil(arr, N, 0, 0);}// Driver Codeint main(){ int arr[] = { 1, 5, 7 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maximumXOR(arr, N); return 0;} |
Java
// Java program for the above approachpublic class GFG{ // Recursive function to find all the // possible breaking of arrays into // subarrays and find the maximum // Bitwise XOR static int maxXORUtil(int arr[], int N, int xrr, int orr) { // If the value of N is 0 if (N == 0) return xrr ^ orr; // Stores the result if the new // group is formed with the first // element as arr[i] int x = maxXORUtil(arr, N - 1, xrr ^ orr, arr[N - 1]); // Stores if the result if the // arr[i] is included in the // last group int y = maxXORUtil(arr, N - 1, xrr, orr | arr[N - 1]); // Returns the maximum of // x and y return Math.max(x, y); } // Function to find the maximum possible // Bitwise XOR of all possible values of // the array after breaking the arrays // into subarrays static int maximumXOR(int arr[], int N) { // Return the result return maxXORUtil(arr, N, 0, 0); } // Driver code public static void main(String[] args) { int arr[] = { 1, 5, 7 }; int N = arr.length; System.out.println(maximumXOR(arr, N)); }}// This code is contributed by abhinavjain194 |
Python3
# C++ program for the above approach# Recursive function to find all the# possible breaking of arrays o# subarrays and find the maximum# Bitwise XORdef maxXORUtil(arr, N, xrr, orr): # If the value of N is 0 if (N == 0): return xrr ^ orr # Stores the result if the new # group is formed with the first # element as arr[i] x = maxXORUtil(arr, N - 1, xrr ^ orr, arr[N - 1]) # Stores if the result if the # arr[i] is included in the # last group y = maxXORUtil(arr, N - 1, xrr, orr | arr[N - 1]) # Returns the maximum of # x and y return max(x, y)# Function to find the maximum possible# Bitwise XOR of all possible values of# the array after breaking the arrays# o subarraysdef maximumXOR(arr, N): # Return the result return maxXORUtil(arr, N, 0, 0)# Driver Codearr = 1, 5, 7N = len(arr)print(maximumXOR(arr, N))# this code is contributed by shivanisinghss2110 |
C#
// C# program for the above approachusing System;class GFG{ // Recursive function to find all the // possible breaking of arrays into // subarrays and find the maximum // Bitwise XOR static int maxXORUtil(int[] arr, int N, int xrr, int orr) { // If the value of N is 0 if (N == 0) return xrr ^ orr; // Stores the result if the new // group is formed with the first // element as arr[i] int x = maxXORUtil(arr, N - 1, xrr ^ orr, arr[N - 1]); // Stores if the result if the // arr[i] is included in the // last group int y = maxXORUtil(arr, N - 1, xrr, orr | arr[N - 1]); // Returns the maximum of // x and y return Math.Max(x, y); } // Function to find the maximum possible // Bitwise XOR of all possible values of // the array after breaking the arrays // into subarrays static int maximumXOR(int[] arr, int N) { // Return the result return maxXORUtil(arr, N, 0, 0); }// Driver codestatic void Main(){ int[] arr = { 1, 5, 7 }; int N = arr.Length; Console.Write(maximumXOR(arr, N));}}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript program for the above approach// Recursive function to find all the// possible breaking of arrays into// subarrays and find the maximum// Bitwise XORfunction maxXORUtil(arr,N,xrr,orr){ // If the value of N is 0 if (N == 0) return xrr ^ orr; // Stores the result if the new // group is formed with the first // element as arr[i] let x = maxXORUtil(arr, N - 1, xrr ^ orr, arr[N - 1]); // Stores if the result if the // arr[i] is included in the // last group let y = maxXORUtil(arr, N - 1, xrr, orr | arr[N - 1]); // Returns the maximum of // x and y return Math.max(x, y);}// Function to find the maximum possible// Bitwise XOR of all possible values of// the array after breaking the arrays// into subarraysfunction maximumXOR(arr,N){ // Return the result return maxXORUtil(arr, N, 0, 0);}// Driver codelet arr=[1, 5, 7 ];let N = arr.length;document.write(maximumXOR(arr, N));// This code is contributed by unknown2108</script> |
Output:
7
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by observing the relationship between the Bitwise XOR and Bitwise OR i.e., the value of Bitwise XOR of N elements is at most the value of Bitwise OR of N elements. Therefore, to find the maximum value, the idea is to split the group into only 1 group of the whole array.
Hence, print the value of Bitwise OR of the array elements arr[] as the resultant maximum value.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the bitwise OR of// array elementsint MaxXOR(int arr[], int N){ // Stores the resultant maximum // value of Bitwise XOR int res = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { res |= arr[i]; } // Return the maximum value res return res;}// Driver Codeint main(){ int arr[] = { 1, 5, 7 }; int N = sizeof(arr) / sizeof(arr[0]); cout << MaxXOR(arr, N); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{ // Function to find the bitwise OR of// array elementsstatic int MaxXOR(int arr[], int N){ // Stores the resultant maximum // value of Bitwise XOR int res = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { res |= arr[i]; } // Return the maximum value res return res;}public static void main(String[] args){ int arr[] = { 1, 5, 7 }; int N = arr.length; System.out.println(MaxXOR(arr, N));}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to find the bitwise OR of# array elementsdef MaxXOR(arr, N): # Stores the resultant maximum # value of Bitwise XOR res = 0 # Traverse the array arr[] for i in range(N): res |= arr[i] # Return the maximum value res return res# Driver Codeif __name__ == '__main__': arr = [ 1, 5, 7 ] N = len(arr) print (MaxXOR(arr, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the bitwise OR of// array elementsstatic int MaxXOR(int []arr, int N){ // Stores the resultant maximum // value of Bitwise XOR int res = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { res |= arr[i]; } // Return the maximum value res return res;}public static void Main(String[] args){ int []arr = { 1, 5, 7 }; int N = arr.Length; Console.Write(MaxXOR(arr, N));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to find the bitwise OR of// array elementsfunction MaxXOR(arr, N){ // Stores the resultant maximum // value of Bitwise XOR var res = 0; // Traverse the array arr[] for(var i = 0; i < N; i++) { res |= arr[i]; } // Return the maximum value res return res;}// Driver codevar arr = [ 1, 5, 7 ];var N = arr.length;document.write(MaxXOR(arr, N));// This code is contributed by shivanisinghss2110</script> |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
