Maximize XOR subsequence possible by equidistant elements from both ends
Given an array A[] of size N, find the Maximum Xor Subsequence such that both A [ i ] and A [ N – i – 1 ] belong to this subsequence, where i ranges between [0, N – 1].
Examples:
Input: N = 8, A [ ] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 13
Explanation:
Maximum Xor Subsequence is {1, 3, 4, 5, 6, 8}Input: N = 5, A [ ] = {3, 2, 6, 5, 4}
Output: 6
Explanation:
Maximum Xor Subsequence is {3, 2, 6, 5, 4}
Approach:
Since, both A[i] and A[N-i-1] should be present in the same subsequence, pair them up and then find maximum xor sum. For each valid index i, calculate (A[i] ^ A[N-i-1]) and store it in new array X. Size of this new array will be N/2.
Naive Solution:
The simplest approach after creating array X[] for this problem is to recursively generate all subsequences of X and find the maximum xor subsequence.
Following is the recursive definition of maxXorSubseq(X, N, i):
maxXorSubseq ( X, N, i ) = MAX ( X[ i ] ^ maxXorSubseq ( X, N, i + 1 ), maxXorSubseq (X, N, i + 1) )
The total possible combinations will be 2N.
Time Complexity: O(2N)
Below is the implementation of the above approach:
C++
// C++ implementation // of the above approach #include <bits/stdc++.h> using namespace std; // Returns maximum xor int maxXorSubseq(vector< int > &x, int n, int i) { if (i == n) return 0; return max(x[i] ^ maxXorSubseq(x, n, i + 1), maxXorSubseq(x, n, i + 1)); } vector< int > compute(vector< int > a, int n) { vector< int > x; // Calculate a[i]^a[n-i-1] for ( int i = 0; i < n / 2; i++) x.push_back(a[i] ^ a[n - i - 1]); // If n is odd if (n & 1) x.push_back(a[n / 2]); return x; } // Driver code int main() { int n = 8; vector< int > a = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Getting new array x vector< int > x = compute(a, n); int mxXor = maxXorSubseq(x, x.size(), 0); cout << (mxXor); return 0; } // This code is contributed by mohit kumar 29 |
Java
// Java implementation // of the above approach import java.util.*; class GFG{ // Returns maximum xor static int maxXorSubseq(List<Integer> x, int n, int i) { if (i == n) return 0 ; return Math.max(x.get(i) ^ maxXorSubseq(x, n, i + 1 ), maxXorSubseq(x, n, i + 1 )); } static List<Integer> compute(List<Integer> a, int n) { List<Integer> x = new ArrayList<Integer>(); // Calculate a[i]^a[n-i-1] for ( int i = 0 ; i < n / 2 ; i++) x.add(a.get(i) ^ a.get(n - i - 1 )); // If n is odd if ((n & 1 ) == 1 ) x.add(a.get(n / 2 )); return x; } // Driver code public static void main(String[] args) { int n = 8 ; List<Integer> a = Arrays.asList( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ); // Getting new array x List<Integer> x = compute(a, n); int mxXor = maxXorSubseq(x, x.size(), 0 ); System.out.println((mxXor)); } } // This code is contributed by offbeat |
Python3
# Python3 implementation # of the above approach # Returns maximum xor def maxXorSubseq(x, n, i): if (i = = n): return 0 return max ( x[i]^maxXorSubseq( x, n, i + 1 ), maxXorSubseq( x, n, i + 1 )) def compute(a, n): x = [] # Calculate a[i]^a[n-i-1] for i in range (n / / 2 ): x.append(a[i]^a[n - i - 1 ]) # If n is odd if (n& 1 ): x.append(a[n / / 2 ]) return x # Driver code if __name__ = = "__main__" : n = 8 a = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] # Getting new array x x = compute(a, n) mxXor = maxXorSubseq(x, len (x), 0 ) print (mxXor) |
C#
// C# implementation // of the above approach using System; using System.Collections.Generic; class GFG { // Returns maximum xor static int maxXorSubseq(List< int > x, int n, int i) { if (i == n) return 0; return Math.Max(x[i] ^ maxXorSubseq(x, n, i + 1), maxXorSubseq(x, n, i + 1)); } static List< int > compute(List< int > a, int n) { List< int > x = new List< int >(); // Calculate a[i]^a[n-i-1] for ( int i = 0; i < n / 2; i++) x.Add(a[i] ^ a[n - i - 1]); // If n is odd if ((n & 1) == 1) x.Add(a[n / 2]); return x; } static void Main() { int n = 8; List< int > a = new List< int >{ 1, 2, 3, 4, 5, 6, 7, 8 }; // Getting new array x List< int > x = compute(a, n); int mxXor = maxXorSubseq(x, x.Count, 0); Console.WriteLine((mxXor)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript implementation // of the above approach // Returns maximum xor function maxXorSubseq(x, n, i) { if (i == n) return 0; return Math.max(x[i] ^ maxXorSubseq(x, n, i + 1), maxXorSubseq(x, n, i + 1)); } function compute(a, n) { let x = []; // Calculate a[i]^a[n-i-1] for (let i = 0; i < parseInt(n / 2, 10); i++) x.push(a[i] ^ a[n - i - 1]); // If n is odd if ((n & 1) == 1) x.push(a[parseInt(n / 2, 10)]); return x; } let n = 8; let a = [ 1, 2, 3, 4, 5, 6, 7, 8 ]; // Getting new array x let x = compute(a, n); let mxXor = maxXorSubseq(x, x.length, 0); document.write((mxXor)); </script> |
13
Time Complexity: O(2n)
Auxiliary Space: O(N)
Efficient Approach:
Considering the above implementation, the following is a partial recursion tree for input X = [9, 5, 1]
In the above partial recursion tree, maxXorSubseq({1}) is being solved four times. On drawing the complete recursion tree, it can be observed that there are many subproblems that are solved again and again. So this problem has Overlapping Subproblems and recomputation of the same subproblems can be avoided by using Memoization.
For memoization, create an array dp [ ] array and store:
dp[i] = max(x[i] ^ maxXorSubseq(x, n, i + 1), maxXorSubseq(x, n, idx + 1)
This avoids recalculation for previously calculated indices thus optimizing computational complexity.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; vector< int > dp; // Returns maximum xor sum int maxXorSubseq(vector< int > x, int n, int idx) { if (idx == n) { return 0; } // If already precomputed if (dp[idx] != -1) { return dp[idx]; } int ans = 0; ans = max(ans, x[idx] ^ maxXorSubseq(x, n, idx + 1)); ans = max(ans, maxXorSubseq(x, n, idx + 1)); // Store the maximum dp[idx] = ans; return ans; } vector< int > compute( int a[], int n) { vector< int > x; // Calculate a[i]^a[n-i-1] for ( int i = 0; i < n / 2; i++) { x.push_back(a[i] ^ a[n - i - 1]); } // If n is odd if ((n & 1) != 0) { x.push_back(a[n / 2]); } return x; } // Driver code int main() { int n = 8; int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Getting new array x vector< int > x = compute(a, n); // Initialize dp array for ( int i = 0; i < x.size(); i++) { dp.push_back(-1); } int mxXor = maxXorSubseq(x, x.size(), 0); cout << mxXor << endl; return 0; } // This code is contributed by divyesh072019. |
Java
// Java implementation of the above approach import java.io.*; import java.util.*; class GFG{ static Vector<Integer> dp = new Vector<Integer>(); // Returns maximum xor sum static int maxXorSubseq(Vector<Integer> x, int n, int idx) { if (idx == n) { return 0 ; } // If already precomputed if (dp.get(idx) != - 1 ) { return dp.get(idx); } int ans = 0 ; ans = Math.max(ans, x.get(idx) ^ maxXorSubseq(x, n, idx + 1 )); ans = Math.max(ans, maxXorSubseq(x, n, idx + 1 )); // Store the maximum dp.set(idx,ans); return ans; } static Vector<Integer> compute( int [] a, int n) { Vector<Integer> x = new Vector<Integer>(); // Calculate a[i]^a[n-i-1] for ( int i = 0 ; i < n / 2 ; i++) { x.add(a[i] ^ a[n - i - 1 ]); } // If n is odd if ((n & 1 ) != 0 ) { x.add(a[n / 2 ]); } return x; } // Driver code public static void main(String[] args) { int n = 8 ; int [] a = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }; // Getting new array x Vector<Integer> x = compute(a, n); // Initialize dp array for ( int i = 0 ; i < x.size(); i++) { dp.add(- 1 ); } int mxXor = maxXorSubseq(x, x.size(), 0 ); System.out.println(mxXor); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation # of the above approach # Returns maximum xor sum def maxXorSubseq(x, n, idx): if (idx = = n): return 0 # If already precomputed if (dp[idx]! = - 1 ): return dp[idx] ans = 0 ans = max ( ans, x[idx] ^ maxXorSubseq( x, n, idx + 1 )) ans = max (ans, maxXorSubseq( x, n, idx + 1 )) # Store the maximum dp[idx] = ans return ans def compute(a, n): x = [] # Calculate a[i]^a[n-i-1] for i in range (n / / 2 ): x.append(a[i]^a[n - i - 1 ]) # If n is odd if (n& 1 ): x.append(a[n / / 2 ]) return x # Declared dp[] array globally dp = [] # Driver code if __name__ = = "__main__" : n = 8 a = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] # Getting new array x x = compute(a, n) # Initialize dp array dp = [ - 1 for i in range ( len (x))] mxXor = maxXorSubseq(x, len (x), 0 ) print (mxXor) |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG { static List< int > dp = new List< int >(); // Returns maximum xor sum static int maxXorSubseq(List< int > x, int n, int idx) { if (idx == n) { return 0; } // If already precomputed if (dp[idx] != -1) { return dp[idx]; } int ans = 0; ans = Math.Max(ans, x[idx]^maxXorSubseq(x, n, idx + 1)); ans = Math.Max(ans, maxXorSubseq(x, n, idx + 1)); // Store the maximum dp[idx] = ans; return ans; } static List< int > compute( int [] a, int n) { List< int > x = new List< int >(); // Calculate a[i]^a[n-i-1] for ( int i = 0; i < n / 2; i++) { x.Add(a[i] ^ a[n - i - 1]); } // If n is odd if ((n & 1) != 0) { x.Add(a[n / 2]); } return x; } // Driver code static public void Main () { int n = 8; int [] a = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Getting new array x List< int > x = compute(a, n); // Initialize dp array for ( int i = 0; i < x.Count; i++) { dp.Add(-1); } int mxXor = maxXorSubseq(x, x.Count, 0); Console.WriteLine(mxXor); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript implementation of the above approach let dp = []; // Returns maximum xor sum function maxXorSubseq(x, n, idx) { if (idx == n) { return 0; } // If already precomputed if (dp[idx] != -1) { return dp[idx]; } let ans = 0; ans = Math.max(ans, x[idx]^maxXorSubseq(x, n, idx + 1)); ans = Math.max(ans, maxXorSubseq(x, n, idx + 1)); // Store the maximum dp[idx] = ans; return ans; } function compute(a, n) { let x = []; // Calculate a[i]^a[n-i-1] for (let i = 0; i < parseInt(n / 2, 10); i++) { x.push(a[i] ^ a[n - i - 1]); } // If n is odd if ((n & 1) != 0) { x.push(a[n / 2]); } return x; } let n = 8; let a = [ 1, 2, 3, 4, 5, 6, 7, 8 ]; // Getting new array x let x = compute(a, n); // Initialize dp array for (let i = 0; i < x.length; i++) { dp.push(-1); } let mxXor = maxXorSubseq(x, x.length, 0); document.write(mxXor); // This code is contributed by suresh07. </script> |
13
Time complexity: O(N)
Auxiliary Space: O(N)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems.
- Initialize the DP with base cases dp[0]= 0.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[idx].
Implementation :
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; vector< int > dp; // Returns maximum xor sum int maxXorSubseq(vector< int > x, int n, int idx) { // Initialize dp to store // computations of subproblems vector< int > dp(n+1, 0); dp[n] = 0; // Base case // iterate over subproblems and get the current // solution for previous computations for ( int i = n-1; i >= 0; i--) { int ans = 0; ans = max(ans, x[i] ^ dp[i+1]); ans = max(ans, dp[i+1]); // update dp dp[i] = ans; } // return answer return dp[idx]; } vector< int > compute( int a[], int n) { vector< int > x; // Calculate a[i]^a[n-i-1] for ( int i = 0; i < n / 2; i++) { x.push_back(a[i] ^ a[n - i - 1]); } // If n is odd if ((n & 1) != 0) { x.push_back(a[n / 2]); } return x; } // Driver code int main() { int n = 8; int a[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Getting new array x vector< int > x = compute(a, n); // Initialize dp array for ( int i = 0; i < x.size(); i++) { dp.push_back(-1); } int mxXor = maxXorSubseq(x, x.size(), 0); cout << mxXor << endl; return 0; } // This code is contributed by bhardwajji. |
Java
/*package whatever //do not write package name here */ import java.util.*; public class Main { static ArrayList<Integer> dp = new ArrayList<>(); // Returns maximum xor sum public static int maxXorSubseq(ArrayList<Integer> x, int n, int idx) { // Initialize dp to store computations of // subproblems ArrayList<Integer> dp = new ArrayList<>( Collections.nCopies(n + 1 , 0 )); dp.set(n, 0 ); // Base case // iterate over subproblems and get the current // solution for previous computations for ( int i = n - 1 ; i >= 0 ; i--) { int ans = 0 ; ans = Math.max(ans, x.get(i) ^ dp.get(i + 1 )); ans = Math.max(ans, dp.get(i + 1 )); // update dp dp.set(i, ans); } // return answer return dp.get(idx); } public static ArrayList<Integer> compute( int [] a, int n) { ArrayList<Integer> x = new ArrayList<>(); // Calculate a[i]^a[n-i-1] for ( int i = 0 ; i < n / 2 ; i++) { x.add(a[i] ^ a[n - i - 1 ]); } // If n is odd if ((n & 1 ) != 0 ) { x.add(a[n / 2 ]); } return x; } // Driver code public static void main(String[] args) { int n = 8 ; int [] a = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }; // Getting new array x ArrayList<Integer> x = compute(a, n); // Initialize dp array for ( int i = 0 ; i < x.size(); i++) { dp.add(- 1 ); } int mxXor = maxXorSubseq(x, x.size(), 0 ); System.out.println(mxXor); } } //This code is contributed by aeroabrar_31 |
Python3
def maxXorSubseq(x, n, idx): # Initialize dp to store computations of subproblems dp = [ 0 ] * (n + 1 ) dp[n] = 0 # Base case # iterate over subproblems and get the current solution for previous computations for i in range (n - 1 , - 1 , - 1 ): ans = 0 ans = max (ans, x[i] ^ dp[i + 1 ]) ans = max (ans, dp[i + 1 ]) # update dp dp[i] = ans # return answer return dp[idx] def compute(a, n): x = [] # Calculate a[i]^a[n-i-1] for i in range (n / / 2 ): x.append(a[i] ^ a[n - i - 1 ]) # If n is odd if (n % 2 ) ! = 0 : x.append(a[n / / 2 ]) return x # Driver code n = 8 a = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] # Getting new array x x = compute(a, n) # Initialize dp array dp = [ - 1 ] * len (x) mxXor = maxXorSubseq(x, len (x), 0 ) print (mxXor) |
C#
using System; using System.Collections.Generic; public class GFG { static List< int > dp = new List< int >(); // Returns maximum xor sum public static int MaxXorSubseq(List< int > x, int n, int idx) { // Initialize dp to store computations of subproblems List< int > dp = new List< int >( new int [n + 1]); dp[n] = 0; // Base case // iterate over subproblems and get the current solution for previous computations for ( int i = n - 1; i >= 0; i--) { int ans = 0; ans = Math.Max(ans, x[i] ^ dp[i + 1]); ans = Math.Max(ans, dp[i + 1]); // update dp dp[i] = ans; } // return answer return dp[idx]; } public static List< int > Compute( int [] a, int n) { List< int > x = new List< int >(); // Calculate a[i]^a[n-i-1] for ( int i = 0; i < n / 2; i++) { x.Add(a[i] ^ a[n - i - 1]); } // If n is odd if ((n & 1) != 0) { x.Add(a[n / 2]); } return x; } // Driver code public static void Main( string [] args) { int n = 8; int [] a = { 1, 2, 3, 4, 5, 6, 7, 8 }; // Getting new array x List< int > x = Compute(a, n); // Initialize dp array for ( int i = 0; i < x.Count; i++) { dp.Add(-1); } int mxXor = MaxXorSubseq(x, x.Count, 0); Console.WriteLine(mxXor); } } //This code is contributed by aeroabrar_31, GPREC |
Javascript
// Returns maximum xor sum function maxXorSubseq(x, n, idx) { // Initialize dp to store // computations of subproblems let dp = Array(n + 1).fill(0); dp[n] = 0; // Base case // iterate over subproblems and get the current // solution for previous computations for (let i = n - 1; i >= 0; i--) { let ans = 0; ans = Math.max(ans, x[i] ^ dp[i + 1]); ans = Math.max(ans, dp[i + 1]); // update dp dp[i] = ans; } // return answer return dp[idx]; } function compute(a, n) { let x = []; // Calculate a[i]^a[n-i-1] for (let i = 0; i < n / 2; i++) { x.push(a[i] ^ a[n - i - 1]); } // If n is odd if ((n & 1) != 0) { x.push(a[n / 2]); } return x; } // Driver code let n = 8; let a = [1, 2, 3, 4, 5, 6, 7, 8]; // Getting new array x let x = compute(a, n); // Initialize dp array let dp = []; for (let i = 0; i < x.length; i++) { dp.push(-1); } let mxXor = maxXorSubseq(x, x.length, 0); console.log(mxXor); |
13
Time complexity: O(N)
Auxiliary Space: O(N)
Contact Us