CODEWITHSUNDEEP
algorithmxorsubsequence
Deepak Yadav
Deepak Yadav

Reputation: 97

Maximum length of the subsequence such that the bitwise XOR of each consecutive element is is k

I am trying to solve this question where we have to find the maximum length of the subsequence such that XOR of each consecutive element is equal to k. e.g : Array = [3,2,4,3,5] and k=1. Answer would be 3. subsequence = [3,2,3]

So far I have tried these approaches :

  1. Naive two-loop solution where we will use two loops and find the subsequence with XOR equals to k.This approach is giving me timeout as the number of elements in the array can be up to 10^5.Psuedo Code :
int finalAns=0;
loop (i=0...n):
  int xortillnow = array[i], count=1;  // since we have already selected one element
  loop(j=i+1..n):
      if((xortillnow ^ array[i])==k):
          count++;
          xortillnow = xortillnow ^ array[i];
   finalAns = max(count,finalAns);

2.Second I am thinking of dynamic programming where I can store XOR of already calculated subsequence but I am not able to complete the algorithm.

Can someone please tell some other way of solving this problem.

Upvotes: 4

Views: 4664

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

The XOR operator has the nice property that, for any value x, there is exactly one value y where x ⊕ y = k. Specifically, that value y is given by x ⊕ k, since

(x ⊕ k) ⊕ k = x ⊕ (k ⊕ k) = x ⊕ 0 = x.

So imagine scanning the array from the left to the right. Each time you see a new element, it can either

  1. Be the start of a new subsequence which at present has length 1, or
  2. Continue an existing subsequence, but only if x ⊕ k appears before it in the sequence. And if x ⊕ k does appear, the length of the subsequence would be equal to one plus the length of the longest subsequence with this property ending at x ⊕ k.

This gives a relatively simple algorithm for this problem. Maintain a hash table or BST mapping previously-seen values to the maximum length of a subsequence with this property ending at that value. Scan from left to right across the array. For each element x, compute x ⊕ k and check if it’s in the table. If so, record that x has length m + 1, where m was the length stored for x ⊕ k. If not, record that x has length 1.

This takes deterministic time O(n log n) using a BST and expected time O(n) using a hash table.

Upvotes: 9

Related Questions