Mathworks EDG
leetcode150
199
CareerInterview

image.png

From the question we can observe that..

image.png

So , the subsequence is nothing but alternate values ..

So ,we need to find the pairs of them..

So , Suppose we are at a value x , then ending at x , max length of subsequence can be defined as 1 + dp[x ^ target] ;

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int longestXORSubsequence(const vector<int>& arr, int k) {
    unordered_map<int, int> dp;
    int maxLength = 1;

    for (int num : arr) {
        int partner = num ^ k;
        dp[num] = max(dp[num],1 + dp[partner]);
        maxLength = max(maxLength,dp[num]);
    }

    return maxLength;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int& x : arr) cin >> x;

    cout << longestXORSubsequence(arr, k) << endl;

    return 0;
}
Comments (1)