Find a partition point in array to maximize its xor sum
Given an array a of size N. The task is to find an index ‘i’ (1 <= i <= N) such that (a[1] ^ … ^ a[i]) + (a[i+1] ^ … ^ a[N]) (x^y represents the xor value of x and y) is maximum possible.
Examples:
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
Naive Approach: A naive approach is to use nested loops. Traverse the array and find the xor of the array till the i’th index and find the xor of elements from index i+1 to and calculate the maximum sum possible.
Below is the implementation of the above approach:
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> |
2
Time complexity: O( N^2 )
Auxiliary space: O(1)
Efficient Approach: An efficient approach is to use a prefix xor array. At any index ‘i’ PrefixXor[i] gives us arr[1] ^ arr[1] ^….^ arr[i] and to get arr[i+1] ^ arr[i+2] ^ . . ^ arr[n-1], find PrefixXor[i] ^ PrefixXor[n] .
Below is the implementation of the above approach:
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> |
2
Time complexity: O(N) where N is the size of the given array
Auxiliary space: O(N)
Contact Us