Dada una array arr[] que consta de N enteros, la tarea es encontrar el máximo Bitwise XOR de Bitwise OR de cada subarreglo después de dividir el arreglo en subarreglos (posibles ceros subarreglos).
Ejemplos:
Entrada: arr[] = {1, 5, 7}, N = 3
Salida: 7
Explicación:
La array dada se puede expresar como el 1 subarreglo, es decir, {1, 5, 7}.
El Bitwise XOR del Bitwise OR del subarreglo formado es 7, que es el valor máximo posible.Entrada: arr[] = {1, 2}, N = 2
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema anterior es generar todas las combinaciones posibles de ruptura de subarreglos usando recursividad y en cada llamada recursiva, encontrar el valor máximo de Bitwise XOR de Bitwise OR de todos los subarreglos formados posibles e imprimirlo.
A continuación se muestra la implementación del enfoque anterior:
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 XOR
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 max(x, y);
}
// Function to find the maximum possible
// Bitwise XOR of all possible values of
// the array after breaking the arrays
// into subarrays
int maximumXOR(int arr[], int N)
{
// Return the result
return maxXORUtil(arr, N, 0, 0);
}
// Driver Code
int 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 approach
public 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 XOR def 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 subarrays def maximumXOR(arr, N): # Return the result return maxXORUtil(arr, N, 0, 0) # Driver Code arr = 1, 5, 7 N = len(arr) print(maximumXOR(arr, N)) # this code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using 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 code
static 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 XOR
function 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 subarrays
function maximumXOR(arr,N)
{
// Return the result
return maxXORUtil(arr, N, 0, 0);
}
// Driver code
let arr=[1, 5, 7 ];
let N = arr.length;
document.write(maximumXOR(arr, N));
// This code is contributed by unknown2108
</script>
Producción:
7
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar observando la relación entre Bitwise XOR y Bitwise OR , es decir, el valor de Bitwise XOR de N elementos es como máximo el valor de Bitwise OR de N elementos. Por lo tanto, para encontrar el valor máximo, la idea es dividir el grupo en solo 1 grupo de toda la array.
Por lo tanto, imprima el valor de Bitwise OR de los elementos de la array arr[] como el valor máximo resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the bitwise OR of
// array elements
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;
}
// Driver Code
int 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 approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the bitwise OR of
// array elements
static 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 elements def 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 Code if __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 approach
using System;
class GFG
{
// Function to find the bitwise OR of
// array elements
static 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 elements
function 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 code
var arr = [ 1, 5, 7 ];
var N = arr.length;
document.write(MaxXOR(arr, N));
// This code is contributed by shivanisinghss2110
</script>
Producción:
7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)