Given an array arr[] of N non-negative integers and an integer K, the idea is to find the length of the longest subsequence having Xor of adjacent elements equal to K.
Examples:
Input: N = 5, arr[] = {3, 2, 4, 3, 5}, K = 1
Output: 3
Explanation:
All the subsequences having Xor of adjacent element equal to K are {3, 2}, {2, 3}, {4, 5}, {3, 2, 3}.
Therefore, the length of the longest subsequence having xor of adjacent element as 1 is 3.Input: N = 8, arr[] = {4, 5, 4, 7, 3, 5, 4, 6}, K = 2
Output: 3
Explanation:
All the subsequences having Xor of adjacent element equal to K are {4, 6}, {5, 7}, {7, 5}, {5, 7, 5}.
Therefore, the length of the longest subsequence having xor of adjacent element as 1 is 3
Naive Approach: The idea is to use Dynamic Programming. The given problem can be solved based on the following observations:
- Suppose Dp(i) represent maximum length of subsequence ending at index i.
- Then, transition of one state to another state will be as follows:
- Find index j such that j < i and a[j] ^ a[i] = k.
- Therefore, Dp(i) = max(Dp(j)+1, Dp(i))
Follow the steps below to solve the problem:
- Initialize an integer, say ans, to store the length of the longest subsequence and an array, say dp[], to store the dp states.
- Define base case as dp[0] = 1.
- Iterate over the range [1, N – 1]:
- Iterate over the range [0, i-1] and update dp[i] as max(dp[i], dp[j] + 1) if a[i] ^ a[j] = K.
- Update ans as max(ans, dp[i]).
- Finally, print the maximum length of the longest subsequence ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum length// of subsequence having XOR of// adjacent elements equal to Kint xorSubsequence(int a[], int n, int k){ // Store maximum length of subsequence int ans = 0; // Stores the dp-states int dp[n] = {0}; // Base case dp[0] = 1; // Iterate over the range [1, N-1] for (int i = 1; i < n; i++) { // Iterate over the range [0, i - 1] for (int j = i - 1; j >= 0; j--) { // If arr[i]^arr[j] == K if ((a[i] ^ a[j]) == k) // Update the dp[i] dp[i] = max(dp[i], dp[j] + 1); } // Update the maximum subsequence length ans = max(ans, dp[i]); dp[i] = max(1, dp[i]); } // If length of longest subsequence // is less than 2 then return 0 return ans >= 2 ? ans : 0;}// Driver Codeint main(){ // Input int arr[] = { 3, 2, 4, 3, 5 }; int K = 1; int N = sizeof(arr) / sizeof(arr[0]); // Print the length of longest subsequence cout << xorSubsequence(arr, N, K); return 0;}// This code is contributed by Dharanendra L V |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find maximum length // of subsequence having XOR of // adjacent elements equal to K public static int xorSubsequence(int a[], int n, int k) { // Store maximum length of subsequence int ans = 0; // Stores the dp-states int dp[] = new int[n]; // Base case dp[0] = 1; // Iterate over the range [1, N-1] for (int i = 1; i < n; i++) { // Iterate over the range [0, i - 1] for (int j = i - 1; j >= 0; j--) { // If arr[i]^arr[j] == K if ((a[i] ^ a[j]) == k) // Update the dp[i] dp[i] = Math.max(dp[i], dp[j] + 1); } // Update the maximum subsequence length ans = Math.max(ans, dp[i]); dp[i] = Math.max(1, dp[i]); } // If length of longest subsequence // is less than 2 then return 0 return ans >= 2 ? ans : 0; } // Driver Code public static void main(String[] args) { // Input int arr[] = { 3, 2, 4, 3, 5 }; int K = 1; int N = arr.length; // Print the length of longest subsequence System.out.println(xorSubsequence(arr, N, K)); }} |
Python3
# Python program for the above approach# Function to find maximum length# of subsequence having XOR of# adjacent elements equal to Kdef xorSubsequence(a, n, k): # Store maximum length of subsequence ans = 0; # Stores the dp-states dp = [0] * n; # Base case dp[0] = 1; # Iterate over the range [1, N-1] for i in range(1, n): # Iterate over the range [0, i - 1] for j in range(i - 1, -1, -1): # If arr[i]^arr[j] == K if ((a[i] ^ a[j]) == k): # Update the dp[i] dp[i] = max(dp[i], dp[j] + 1); # Update the maximum subsequence length ans = max(ans, dp[i]); dp[i] = max(1, dp[i]); # If length of longest subsequence # is less than 2 then return 0 return ans if ans >= 2 else 0;# Driver Codeif __name__ == '__main__': # Input arr = [3, 2, 4, 3, 5]; K = 1; N = len(arr); # Print the length of longest subsequence print(xorSubsequence(arr, N, K)); # This code contributed by shikhasingrajput |
C#
// C# program of the above approachusing System;class GFG{ // Function to find maximum length // of subsequence having XOR of // adjacent elements equal to K static int xorSubsequence(int[] a, int n, int k) { // Store maximum length of subsequence int ans = 0; // Stores the dp-states int[] dp = new int[n]; // Base case dp[0] = 1; // Iterate over the range [1, N-1] for(int i = 1; i < n; i++) { // Iterate over the range [0, i - 1] for(int j = i - 1; j >= 0; j--) { // If arr[i]^arr[j] == K if ((a[i] ^ a[j]) == k) // Update the dp[i] dp[i] = Math.Max(dp[i], dp[j] + 1); } // Update the maximum subsequence length ans = Math.Max(ans, dp[i]); dp[i] = Math.Max(1, dp[i]); } // If length of longest subsequence // is less than 2 then return 0 return ans >= 2 ? ans : 0; } // Driver code static void Main() { // Input int[] arr = { 3, 2, 4, 3, 5 }; int K = 1; int N = arr.Length; // Print the length of longest subsequence Console.WriteLine(xorSubsequence(arr, N, K)); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program of the above approach // Function to find maximum length // of subsequence having XOR of // adjacent elements equal to K function xorSubsequence(a, n, k) { // Store maximum length of subsequence let ans = 0; // Stores the dp-states let dp = new Array(n); dp.fill(0); // Base case dp[0] = 1; // Iterate over the range [1, N-1] for(let i = 1; i < n; i++) { // Iterate over the range [0, i - 1] for(let j = i - 1; j >= 0; j--) { // If arr[i]^arr[j] == K if ((a[i] ^ a[j]) == k) // Update the dp[i] dp[i] = Math.max(dp[i], dp[j] + 1); } // Update the maximum subsequence length ans = Math.max(ans, dp[i]); dp[i] = Math.max(1, dp[i]); } // If length of longest subsequence // is less than 2 then return 0 return ans >= 2 ? ans : 0; } let arr = [ 3, 2, 4, 3, 5 ]; let K = 1; let N = arr.length; // Print the length of longest subsequence document.write(xorSubsequence(arr, N, K)); </script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by using the property of Xor and Hashmap with dynamic programming to store the maximum length of subsequence ending at an integer, resulting in constant time transition of states in DP.
- Initialize an integer say ans =0 to store the length of the longest subsequence and an array say dp[] to store the state of DP.
- Initialize a HashMap say mp to store the longest length of subsequence ending at an element.
- Define base case as dp[0] = 1 and push the pair {arr[0], 1} in mp.
- Iterate over the range [1, N-1]:
- Find the length of the longest subsequence say dpj ending at element arr[i] ^K from HashMap mp.
- Update dp[i] as max(dp[i], dpj+1) and update the longest length of subsequence ending at element arr[i] in HashMap mp.
- Update the ans = max(ans, dp[i]).
- Finally, print the maximum length of the longest subsequence ans.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum length of subsequenceint xorSubsequence(int a[], int n, int k){ // Stores maximum length of subsequence int ans = 0; // Dictionary to store the longest length of // subsequence ending at an integer, say X map<int, int> map; // Stores the maximum length of // subsequence ending at index i int dp[n] = {0}; // Base case map[a[0]] = 1; dp[0] = 1; // Iterate over the range [1, N-1] for (int i = 1; i < n; i++) { int dpj; // Retrieve the longest length of // subsequence ending at integer a[]^K if(map.find(a[i] ^ k) != map.end()) { dpj = map[a[i] ^ k]; } else{ dpj = -1; } // If dpj is not NULL if (dpj != 0) // Update dp[i] dp[i] = max(dp[i], dpj + 1); // Update ans ans = max(ans, dp[i]); // Update the maximum length of subsequence // ending at element is a[i] in Dictionary if(map.find(a[i]) != map.end()) { map[a[i]] = max(map[a[i]]+1, dp[i]); } else { map[a[i]] = max(1, dp[i]); } } // Return the ans if ans>=2. // Otherwise, return 0 return ans >= 2 ? ans : 0;} int main(){ // Input int arr[] = { 3, 2, 4, 3, 5 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 1; // Print the length of the longest subsequence cout << (xorSubsequence(arr, N, K)); return 0;}// This code is contributed by divyesh072019. |
Java
// Java program for above approachimport java.io.*;import java.util.*;class GFG{ // Function to find maximum length of subsequence public static int xorSubsequence(int a[], int n, int k) { // Stores maximum length of subsequence int ans = 0; // HashMap to store the longest length of // subsequence ending at an integer, say X HashMap<Integer, Integer> map = new HashMap<>(); // Stores the maximum length of // subsequence ending at index i int dp[] = new int[n]; // Base case map.put(a[0], 1); dp[0] = 1; // Iterate over the range [1, N-1] for (int i = 1; i < n; i++) { // Retrieve the longest length of // subsequence ending at integer a[]^K Integer dpj = map.get(a[i] ^ k); // If dpj is not NULL if (dpj != null) // Update dp[i] dp[i] = Math.max(dp[i], dpj + 1); // Update ans ans = Math.max(ans, dp[i]); // Update the maximum length of subsequence // ending at element is a[i] in HashMap map.put( a[i], Math.max(map.getOrDefault(a[i], 1), dp[i])); } // Return the ans if ans>=2. // Otherwise, return 0 return ans >= 2 ? ans : 0; } // Driver Code public static void main(String[] args) { // Input int arr[] = { 3, 2, 4, 3, 5 }; int N = arr.length; int K = 1; // Print the length of the longest subsequence System.out.println(xorSubsequence(arr, N, K)); }} |
Python3
# Python 3 program for above approach# Function to find maximum length of subsequencedef xorSubsequence( a, n, k): # Stores maximum length of subsequence ans = 0 # HashMap to store the longest length of # subsequence ending at an integer, say X map = {} # Stores the maximum length of # subsequence ending at index i dp = [0]* n # Base case map[a[0]] = 1 dp[0] = 1 # Iterate over the range[1, N-1] for i in range(1, n): # Retrieve the longest length of # subsequence ending at integer a[] ^ K # If dpj is not NULL if (a[i] ^ k in map): # Update dp[i] dp[i] = max(dp[i], map[a[i] ^ k] + 1) # Update ans ans = max(ans, dp[i]) # Update the maximum length of subsequence # ending at element is a[i] in HashMap if a[i] in map: map[a[i]] = max(map[a[i]],dp[i]) else: map[a[i]] = max(1, dp[i]) # Return the ans if ans >= 2. # Otherwise, return 0 if ans >= 2 : return ans return 0# Driver Codeif __name__ == "__main__": # Input arr = [3, 2, 4, 3, 5] N = len(arr) K = 1 # Print the length of the longest subsequence print(xorSubsequence(arr, N, K)) # This code is contributed by chitranayal. |
C#
// C# program for above approachusing System;using System.Collections.Generic;public class GFG { // Function to find maximum length of subsequence public static int xorSubsequence(int []a, int n, int k) { // Stores maximum length of subsequence int ans = 0; // Dictionary to store the longest length of // subsequence ending at an integer, say X Dictionary<int, int> map = new Dictionary<int, int>(); // Stores the maximum length of // subsequence ending at index i int []dp = new int[n]; // Base case map.Add(a[0], 1); dp[0] = 1; // Iterate over the range [1, N-1] for (int i = 1; i < n; i++) { // Retrieve the longest length of // subsequence ending at integer []a^K int dpj = map.ContainsKey(a[i] ^ k)?map[a[i] ^ k]:-1; // If dpj is not NULL if (dpj != 0) // Update dp[i] dp[i] = Math.Max(dp[i], dpj + 1); // Update ans ans = Math.Max(ans, dp[i]); // Update the maximum length of subsequence // ending at element is a[i] in Dictionary if(map.ContainsKey(a[i])) { map[a[i]] = Math.Max(map[a[i]]+1, dp[i]); ; } else { map.Add(a[i], Math.Max(1, dp[i])); } } // Return the ans if ans>=2. // Otherwise, return 0 return ans >= 2 ? ans : 0; } // Driver Code public static void Main(String[] args) { // Input int []arr = { 3, 2, 4, 3, 5 }; int N = arr.Length; int K = 1; // Print the length of the longest subsequence Console.WriteLine(xorSubsequence(arr, N, K)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for above approach// Function to find maximum length of subsequencefunction xorSubsequence(a, n, k){ // Stores maximum length of subsequence var ans = 0; // Dictionary to store the longest length of // subsequence ending at an integer, say X var map = new Map(); // Stores the maximum length of // subsequence ending at index i var dp = Array(n).fill(0); // Base case map.set(a[0], 1) dp[0] = 1; // Iterate over the range [1, N-1] for (var i = 1; i < n; i++) { var dpj; // Retrieve the longest length of // subsequence ending at integer []a^K if(map.has(a[i] ^ k)) { dpj = map.get(a[i] ^ k); } else{ dpj = -1; } // If dpj is not NULL if (dpj != 0) // Update dp[i] dp[i] = Math.max(dp[i], dpj + 1); // Update ans ans = Math.max(ans, dp[i]); // Update the maximum length of subsequence // ending at element is a[i] in Dictionary if(map.has(a[i])) { map.set(a[i] , Math.max(map.get(a[i])+1, dp[i])); } else { map.set(a[i], Math.max(1, dp[i])); } } // Return the ans if ans>=2. // Otherwise, return 0 return ans >= 2 ? ans : 0;} // Inputvar arr = [3, 2, 4, 3, 5];var N = arr.length;var K = 1;// Print the length of the longest subsequencedocument.write(xorSubsequence(arr, N, K));// This code is contributed by famously.</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
