Length of the longest subsequence such that XOR of adjacent elements is equal to K | C ++ program for above approach ; Function to find maximum length of subsequence ; Stores maximum length of subsequence ; Dictionary to store the longest length of subsequence ending at an integer , say X ; Stores the maximum length of subsequence ending at index i ; Base case ; Iterate over the range [ 1 , N - 1 ] ; Retrieve the longest length of subsequence ending at integer [ ] a ^ K ; If dpj is not NULL ; Update dp [ i ] ; Update ans ; Update the maximum length of subsequence ending at element is a [ i ] in Dictionary ; Return the ans if ans >= 2. Otherwise , return 0 ; Input ; Print the length of the longest subsequence
#include <bits/stdc++.h> NEW_LINE using namespace std ; int xorSubsequence ( int a [ ] , int n , int k ) { int ans = 0 ; map < int , int > map ; int dp [ n ] = { 0 } ; map [ a [ 0 ] ] = 1 ; dp [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { int dpj ; if ( map . find ( a [ i ] ^ k ) != map . end ( ) ) { dpj = map [ a [ i ] ^ k ] ; } else { dpj = -1 ; } if ( dpj != 0 ) dp [ i ] = max ( dp [ i ] , dpj + 1 ) ; ans = max ( ans , dp [ i ] ) ; 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 ans >= 2 ? ans : 0 ; } int main ( ) { int arr [ ] = { 3 , 2 , 4 , 3 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 1 ; cout << ( xorSubsequence ( arr , N , K ) ) ; return 0 ; }