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-decreasingint 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 codeint 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 approachimport 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-decreasingdef 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 codearr = [ 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 approachusing 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-decreasingfunction 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 codelet 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> |
5
Time Complexity: O(N* N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
