abhinavxd's blog

By abhinavxd, history, 4 years ago, In English

Find the maximum length of the subsequence such that XOR of each consecutive element is equal to k. example: [3,2,4,3,5] and k=1. Answer = 3, subsequence = [3,2,3]

And for [1,2,5,7,9,8,5] ans would be 3.

So far I have tried these approaches :

A naive two-loop solution where we will use two loops and find the subsequence with XOR equals to k.

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 me some other way of solving this problem?

Thanks

  • Vote: I like it
  • -4
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

If consecutive 2 elements are x and y then x^y=k, that means k^x=y, then it means you will have array with period of 2 like [3,2,3,2,3,2], i think this can be easily solved for every pair $$$O(N)$$$ or $$$O(Nlog(N)$$$ by two pointers

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Calculate $$$pref[N$$$] where $$$pref[i] = a_0 ⊕ a_1 ⊕ ... ⊕ a_i$$$. Then for each prefix $$$i$$$ we can find shortest inner prefix $$$j$$$ such that $$$a_{j+1} ⊕ ... ⊕ a_i$$$. Create map<int, int> $$$m$$$ and for each possible $$$x$$$ store smallest $$$i$$$ such that $$$pref[i] = x$$$. Now iterate $$$i = 0...n-1$$$ and for each $$$i$$$ if $$$k ⊕ pref[i]$$$ is present in $$$m$$$ then say $$$ans = max(ans, i - m[k ⊕ pref[i]] + 1)$$$