Length of the longest subsequence such that xor of adjacent elements is non-decreasing
Given a sequence arr of N positive integers, the task is to find the length of the longest subsequence such that xor of adjacent integers in the subsequence must be non-decreasing.
Examples:
Input: N = 8, arr = {1, 100, 3, 64, 0, 5, 2, 15}
Output: 6
The subsequence of maximum length is {1, 3, 0, 5, 2, 15}
with XOR of adjacent elements as {2, 3, 5, 7, 13}
Input: N = 3, arr = {1, 7, 10}
Output: 3
The subsequence of maximum length is {1, 3, 7}
with XOR of adjacent elements as {2, 4}.
Approach:
- This problem can be solved using dynamic programming where dp[i] will store the length of the longest valid subsequence that ends at index i.
- First, store the xor of all the pairs of elements i.e. arr[i] ^ arr[j] and the pair (i, j) also and then sort them according to the value of xor as they need to be non-decreasing.
- Now if the pair (i, j) is considered then the length of the longest subsequence that ends at j will be max(dp[j], 1 + dp[i]). In this way, calculate the maximum possible value of dp[] array for each position and then take the maximum of them.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find the length of the longest // subsequence such that the XOR of adjacent // elements in the subsequence must // be non-decreasing int LongestXorSubsequence( int arr[], int n) { vector<pair< int , pair< int , int > > > v; for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Computing xor of all the pairs // of elements and store them // along with the pair (i, j) v.push_back(make_pair(arr[i] ^ arr[j], make_pair(i, j))); } } // Sort all possible xor values sort(v.begin(), v.end()); int dp[n]; // Initialize the dp array for ( int i = 0; i < n; i++) { dp[i] = 1; } // Calculating the dp array // for each possible position // and calculating the max length // that ends at a particular index for ( auto i : v) { dp[i.second.second] = max(dp[i.second.second], 1 + dp[i.second.first]); } int ans = 1; // Taking maximum of all position for ( int i = 0; i < n; i++) ans = max(ans, dp[i]); return ans; } // Driver code int main() { int arr[] = { 2, 12, 6, 7, 13, 14, 8, 6 }; int n = sizeof (arr) / sizeof (arr[0]); cout << LongestXorSubsequence(arr, n); return 0; } |
Java
// Java implementation of the approach import java.io.*; import java.util.*; import java.util.stream.Collectors; class GFG { // Function to find the length of the longest // subsequence such that the XOR of adjacent // elements in the subsequence must // be non-decreasing static int LongestXorSubsequence( int [] arr, int n) { List< int []> v = new ArrayList<>(); for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { // Computing xor of all the pairs // of elements and store them // along with the pair (i, j) int [] l1 = { arr[i] ^ arr[j], i, j }; v.add(l1); } } // Sort all possible xor values Comparator< int []> byFirstElement = ( int [] a, int [] b) -> a[ 0 ] - b[ 0 ]; List< int []> v1 = v.stream() .sorted(byFirstElement) .collect(Collectors.toList()); int [] dp = new int [n]; // Initialize the dp array for ( int i = 0 ; i < n; i++) { dp[i] = 1 ; } // Calculating the dp array // for each possible position // and calculating the max length // that ends at a particular index Iterator< int []> iter = v1.iterator(); while (iter.hasNext()) { int [] list = iter.next(); dp[list[ 2 ]] = Math.max(dp[list[ 2 ]], 1 + dp[list[ 1 ]]); } int ans = 1 ; // Taking maximum of all position for ( int i = 0 ; i < n; i++) ans = Math.max(ans, dp[i]); return ans; } public static void main(String[] args) { // Driver code int [] arr = { 2 , 12 , 6 , 7 , 13 , 14 , 8 , 6 }; int n = arr.length; System.out.println(LongestXorSubsequence(arr, n)); } } // this code is contributed by phasing17 |
Python3
# Python3 implementation of the approach # Function to find the length of the longest # subsequence such that the XOR of adjacent # elements in the subsequence must # be non-decreasing def LongestXorSubsequence(arr, n): v = [] for i in range ( 0 , n): for j in range (i + 1 , n): # Computing xor of all the pairs # of elements and store them # along with the pair (i, j) v.append([(arr[i] ^ arr[j]), (i, j)]) # v.push_back(make_pair(arr[i] ^ arr[j], make_pair(i, j))) # Sort all possible xor values v.sort() # Initialize the dp array dp = [ 1 for x in range ( 88 )] # Calculating the dp array # for each possible position # and calculating the max length # that ends at a particular index for a, b in v: dp[b[ 1 ]] = max (dp[b[ 1 ]], 1 + dp[b[ 0 ]]) ans = 1 # Taking maximum of all position for i in range ( 0 , n): ans = max (ans, dp[i]) return ans # Driver code arr = [ 2 , 12 , 6 , 7 , 13 , 14 , 8 , 6 ] n = len (arr) print (LongestXorSubsequence(arr, n)) # This code is contributed by Sanjit Prasad |
C#
// C# implementation of the approach using System; using System.Linq; using System.Collections.Generic; class GFG { // Function to find the length of the longest // subsequence such that the XOR of adjacent // elements in the subsequence must // be non-decreasing static int LongestXorSubsequence( int [] arr, int n) { List< int []> v = new List< int []>(); for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { // Computing xor of all the pairs // of elements and store them // along with the pair (i, j) int [] l1 = { arr[i] ^ arr[j], i, j }; v.Add(l1); } } // Sorting the array by First Value List< int []> v1 = v.OrderBy(a => a[0]) .ThenBy(a => a[1]) .ToList(); int [] dp = new int [n]; // Initialize the dp array for ( int i = 0; i < n; i++) { dp[i] = 1; } // Calculating the dp array // for each possible position // and calculating the max length // that ends at a particular index foreach ( var list in v1) dp[list[2]] = Math.Max(dp[list[2]], 1 + dp[list[1]]); int ans = 1; // Taking maximum of all position for ( int i = 0; i < n; i++) ans = Math.Max(ans, dp[i]); return ans; } public static void Main( string [] args) { // Driver code int [] arr = { 2, 12, 6, 7, 13, 14, 8, 6 }; int n = arr.Length; Console.WriteLine(LongestXorSubsequence(arr, n)); } } // This code is contributed by phasing17 |
Javascript
<script> // Javascript implementation of the approach // Function to find the length of the longest // subsequence such that the XOR of adjacent // elements in the subsequence must // be non-decreasing function LongestXorSubsequence(arr, n) { let v = []; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // Computing xor of all the pairs // of elements and store them // along with the pair (i, j) v.push([arr[i] ^ arr[j], [i, j]]); } } // Sort all possible xor values v.sort((a, b) => a[0] - b[0]); let dp = new Array(n); // Initialize the dp array for (let i = 0; i < n; i++) { dp[i] = 1; } // Calculating the dp array // for each possible position // and calculating the max length // that ends at a particular index for (let i of v) { dp[i[1][1]] = Math.max(dp[i[1][1]], 1 + dp[i[1][0]]); } let ans = 1; // Taking maximum of all position for (let i = 0; i < n; i++) ans = Math.max(ans, dp[i]); return ans; } // Driver code let arr = [2, 12, 6, 7, 13, 14, 8, 6]; let n = arr.length; document.write(LongestXorSubsequence(arr, n)); // This code is contributed by _saurabh_jaiswal. </script> |
Output
5
Time Complexity: O(N* N)
Auxiliary Space: O(N)