Find a partition point in array to maximize its xor sum | CPP program to find partition point in array to maximize xor sum ; Function to calculate Prefix Xor array ; Calculating prefix xor ; Function to find partition point in array to maximize xor sum ; To store prefix xor ; Compute the prefix xor ; To store sum and index ; Calculate the maximum sum that can be obtained splitting the array at some index 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 ; Return the index ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void ComputePrefixXor ( int arr [ ] , int PrefixXor [ ] , int n ) { PrefixXor [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) PrefixXor [ i ] = PrefixXor [ i - 1 ] ^ arr [ i ] ; } int Xor_Sum ( int arr [ ] , int n ) { int PrefixXor [ n ] ; ComputePrefixXor ( arr , PrefixXor , n ) ; int sum = 0 , index ; for ( int i = 0 ; i < n ; i ++ ) { if ( PrefixXor [ i ] + ( PrefixXor [ n - 1 ] ^ PrefixXor [ i ] ) > sum ) { sum = PrefixXor [ i ] + ( PrefixXor [ n - 1 ] ^ PrefixXor [ i ] ) ; index = i ; } } return index + 1 ; } int main ( ) { int arr [ ] = { 1 , 4 , 6 , 3 , 8 , 13 , 34 , 2 , 21 , 10 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << Xor_Sum ( arr , n ) ; return 0 ; }