Dada una array a de tamaño N . La tarea es encontrar un índice ‘i’ (1 <= i <= N) tal que (a[1] ^ … ^ a[i]) + (a[i+1] ^ … ^ a[N]) (x^y representa el valor xor de xey) es el máximo posible.
Ejemplos:
Input : arr[] = {1, 4, 6, 3, 8, 13, 34, 2, 21, 10}
Output : 2
Explanation : The maximum value is 68 at index 2
Input : arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Output : 4
Enfoque ingenuo : un enfoque ingenuo es usar bucles anidados. Recorra la array y encuentre el xor de la array hasta el i-ésimo índice y encuentre el xor de los elementos desde el índice i+1 hasta y calcule la suma máxima posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find partition point in
// array to maximize xor sum
#include <bits/stdc++.h>
using namespace std;
// Function to find partition point in
// array to maximize xor sum
int Xor_Sum(int arr[], int n)
{
int sum = 0, index, left_xor = 0, right_xor = 0;
// Traverse through the array
for (int i = 0; i < n; i++)
{
// Calculate xor of elements left of index i
// including ith element
left_xor = left_xor ^ arr[i];
right_xor = 0;
for (int j = i + 1; j < n; j++)
{
// Calculate xor of the elements right of
// index i
right_xor = right_xor ^ arr[j];
}
// Keep the maximum possible xor sum
if (left_xor + right_xor > sum)
{
sum = left_xor + right_xor;
index = i;
}
}
// Return the 1 based index of the array
return index+1;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 6, 3, 8, 13, 34, 2, 21, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << Xor_Sum(arr, n);
return 0;
}
Java
// Java program to find partition point in
// array to maximize xor sum
class GFG
{
// Function to find partition point in
// array to maximize xor sum
public static int Xor_Sum(int[] arr, int n)
{
int sum = 0, index = -1;
int left_xor = 0, right_xor = 0;
// Traverse through the array
for (int i = 0; i < n; i++)
{
// Calculate xor of elements left of index i
// including ith element
left_xor = left_xor ^ arr[i];
right_xor = 0;
for (int j = i + 1; j < n; j++)
{
// Calculate xor of the elements right of
// index i
right_xor = right_xor ^ arr[j];
}
// Keep the maximum possible xor sum
if (left_xor + right_xor > sum)
{
sum = left_xor + right_xor;
index = i;
}
}
// Return the 1 based index of the array
return index + 1;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 4, 6, 3, 8,
13, 34, 2, 21, 10 };
int n = arr.length;
// Function call
System.out.println(Xor_Sum(arr, n));
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to find partition point in # array to maximize xor sum # Function to find partition point in # array to maximize xor sum def Xor_Sum(arr, n): sum = 0 index, left_xor = 0, 0 right_xor = 0 # Traverse through the array for i in range(n): # Calculate xor of elements left of index i # including ith element left_xor = left_xor ^ arr[i] right_xor = 0 for j in range(i + 1, n): # Calculate xor of the elements # right of index i right_xor = right_xor ^ arr[j] # Keep the maximum possible xor sum if (left_xor + right_xor > sum): sum = left_xor + right_xor index = i # Return the 1 based index of the array return index + 1 # Driver code arr = [ 1, 4, 6, 3, 8, 13, 34, 2, 21, 10] n = len(arr) # Function call print(Xor_Sum(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# program to find partition point in
// array to maximize xor sum
using System;
class GFG
{
// Function to find partition point in
// array to maximize xor sum
public static int Xor_Sum(int[] arr,
int n)
{
int sum = 0, index = -1;
int left_xor = 0, right_xor = 0;
// Traverse through the array
for (int i = 0; i < n; i++)
{
// Calculate xor of elements left of index i
// including ith element
left_xor = left_xor ^ arr[i];
right_xor = 0;
for (int j = i + 1; j < n; j++)
{
// Calculate xor of the elements
// right of index i
right_xor = right_xor ^ arr[j];
}
// Keep the maximum possible xor sum
if (left_xor + right_xor > sum)
{
sum = left_xor + right_xor;
index = i;
}
}
// Return the 1 based index of the array
return index + 1;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 1, 4, 6, 3, 8,
13, 34, 2, 21, 10 };
int n = arr.Length;
// Function call
Console.WriteLine (Xor_Sum(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to
// find partition point in
// array to maximize xor sum
// Function to find partition point in
// array to maximize xor sum
function Xor_Sum(arr, n)
{
let sum = 0, index, left_xor = 0,
right_xor = 0;
// Traverse through the array
for (let i = 0; i < n; i++)
{
// Calculate xor of elements
// left of index i
// including ith element
left_xor = left_xor ^ arr[i];
right_xor = 0;
for (let j = i + 1; j < n; j++)
{
// Calculate xor of the
// elements right of
// index i
right_xor = right_xor ^ arr[j];
}
// Keep the maximum possible xor sum
if (left_xor + right_xor > sum)
{
sum = left_xor + right_xor;
index = i;
}
}
// Return the 1 based index of the array
return index+1;
}
// Driver code
let arr = [ 1, 4, 6, 3, 8, 13, 34, 2, 21, 10 ];
let n = arr.length;
// Function call
document.write(Xor_Sum(arr, n));
</script>
Producción:
2
Complejidad temporal: O( N^2 ).
Enfoque eficiente : un enfoque eficiente es usar una array xor de prefijo. En cualquier índice ‘i’ PrefixXor[i] nos da arr[1] ^ arr[1] ^….^ arr[i] y obtener arr[i+1] ^ arr[i+2] ^ . . ^ arr[n-1] , encuentre PrefixXor[i] ^ PrefixXor[n] .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find partition point in
// array to maximize xor sum
#include <bits/stdc++.h>
using namespace std;
// Function to calculate Prefix Xor array
void ComputePrefixXor(int arr[], int PrefixXor[], int n)
{
PrefixXor[0] = arr[0];
// Calculating prefix xor
for (int i = 1; i < n; i++)
PrefixXor[i] = PrefixXor[i - 1] ^ arr[i];
}
// Function to find partition point in
// array to maximize xor sum
int Xor_Sum(int arr[], int n)
{
// To store prefix xor
int PrefixXor[n];
// Compute the prefix xor
ComputePrefixXor(arr, PrefixXor, n);
// To store sum and index
int sum = 0, index;
// Calculate the maximum sum that can be obtained
// splitting the array at some index i
for (int i = 0; i < n; i++)
{
// PrefixXor[i] = Xor of all arr
// elements till i'th index PrefixXor[n-1]
// ^ PrefixXor[i] = Xor of all elements
// from i+1' th index to n-1'th index
if (PrefixXor[i] + (PrefixXor[n - 1] ^
PrefixXor[i]) > sum)
{
sum = PrefixXor[i] +
(PrefixXor[n - 1] ^ PrefixXor[i]);
index = i;
}
}
// Return the index
return index+1;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 6, 3, 8, 13, 34, 2, 21, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << Xor_Sum(arr, n);
return 0;
}
Java
// Java program to find partition point in
// array to maximize xor sum
import java.util.*;
class GFG
{
// Function to calculate Prefix Xor array
static void ComputePrefixXor(int arr[],
int PrefixXor[],
int n)
{
PrefixXor[0] = arr[0];
// Calculating prefix xor
for (int i = 1; i < n; i++)
PrefixXor[i] = PrefixXor[i - 1] ^ arr[i];
}
// Function to find partition point in
// array to maximize xor sum
static int Xor_Sum(int arr[], int n)
{
// To store prefix xor
int []PrefixXor = new int[n];
// Compute the prefix xor
ComputePrefixXor(arr, PrefixXor, n);
// To store sum and index
int sum = 0, index = 0;
// Calculate the maximum sum that can be obtained
// splitting the array at some index i
for (int i = 0; i < n; i++)
{
// PrefixXor[i] = Xor of all arr
// elements till i'th index PrefixXor[n-1]
// ^ PrefixXor[i] = Xor of all elements
// from i+1' th index to n-1'th index
if (PrefixXor[i] + (PrefixXor[n - 1] ^
PrefixXor[i]) > sum)
{
sum = PrefixXor[i] +
(PrefixXor[n - 1] ^ PrefixXor[i]);
index = i;
}
}
// Return the index
return index+1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 4, 6, 3, 8,
13, 34, 2, 21, 10 };
int n = arr.length;
// Function call
System.out.println(Xor_Sum(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find partition point in # array to maximize xor sum # Function to calculate Prefix Xor array def ComputePrefixXor(arr, PrefixXor, n): PrefixXor[0] = arr[0]; # Calculating prefix xor for i in range(1, n): PrefixXor[i] = PrefixXor[i - 1] ^ arr[i]; # Function to find partition point in # array to maximize xor sum def Xor_Sum(arr, n): # To store prefix xor PrefixXor = [0] * n; # Compute the prefix xor ComputePrefixXor(arr, PrefixXor, n); # To store sum and index sum, index = 0, 0; # Calculate the maximum sum that can be obtained # splitting the array at some index i for i in range(n): # PrefixXor[i] = Xor of all arr # elements till i'th index PrefixXor[n-1] # ^ PrefixXor[i] = Xor of all elements # from i+1' th index to n-1'th index if (PrefixXor[i] + (PrefixXor[n - 1] ^ PrefixXor[i]) > sum): sum = PrefixXor[i] +\ (PrefixXor[n - 1] ^ PrefixXor[i]); index = i; # Return the index return index + 1; # Driver code arr = [ 1, 4, 6, 3, 8, 13, 34, 2, 21, 10 ]; n = len(arr); # Function call print(Xor_Sum(arr, n)); # This code is contributed by Rajput-Ji
C#
// C# program to find partition point in
// array to maximize xor sum
using System;
class GFG
{
// Function to calculate Prefix Xor array
static void ComputePrefixXor(int[] arr,
int[] PrefixXor,
int n)
{
PrefixXor[0] = arr[0];
// Calculating prefix xor
for (int i = 1; i < n; i++)
PrefixXor[i] = PrefixXor[i - 1] ^ arr[i];
}
// Function to find partition point in
// array to maximize xor sum
static int Xor_Sum(int[] arr, int n)
{
// To store prefix xor
int []PrefixXor = new int[n];
// Compute the prefix xor
ComputePrefixXor(arr, PrefixXor, n);
// To store sum and index
int sum = 0, index = 0;
// Calculate the maximum sum that can be obtained
// splitting the array at some index i
for (int i = 0; i < n; i++)
{
// PrefixXor[i] = Xor of all arr
// elements till i'th index PrefixXor[n-1]
// ^ PrefixXor[i] = Xor of all elements
// from i+1' th index to n-1'th index
if (PrefixXor[i] + (PrefixXor[n - 1] ^
PrefixXor[i]) > sum)
{
sum = PrefixXor[i] + (PrefixXor[n - 1] ^
PrefixXor[i]);
index = i;
}
}
// Return the index
return index + 1;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 4, 6, 3, 8,
13, 34, 2, 21, 10 };
int n = arr.Length;
// Function call
Console.WriteLine(Xor_Sum(arr, n));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program to find partition point in
// array to maximize xor sum
// Function to calculate Prefix Xor array
function ComputePrefixXor(arr, PrefixXor, n)
{
PrefixXor[0] = arr[0];
// Calculating prefix xor
for (let i = 1; i < n; i++)
PrefixXor[i] = PrefixXor[i - 1] ^ arr[i];
}
// Function to find partition point in
// array to maximize xor sum
function Xor_Sum(arr, n)
{
// To store prefix xor
let PrefixXor = new Array(n);
// Compute the prefix xor
ComputePrefixXor(arr, PrefixXor, n);
// To store sum and index
let sum = 0, index;
// Calculate the maximum sum that can be obtained
// splitting the array at some index i
for (let i = 0; i < n; i++)
{
// PrefixXor[i] = Xor of all arr
// elements till i'th index PrefixXor[n-1]
// ^ PrefixXor[i] = Xor of all elements
// from i+1' th index to n-1'th index
if (PrefixXor[i] + (PrefixXor[n - 1] ^
PrefixXor[i]) > sum)
{
sum = PrefixXor[i] +
(PrefixXor[n - 1] ^ PrefixXor[i]);
index = i;
}
}
// Return the index
return index+1;
}
// Driver code
let arr = [ 1, 4, 6, 3, 8, 13, 34, 2, 21, 10 ];
let n = arr.length;
// Function call
document.write(Xor_Sum(arr, n));
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por syntaxerror y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA