cryo_coder123's blog

A beautiful probem on XOR ....
By cryo_coder123, history, 4 years ago, In English

Recently one of my friends shared this problem with me. I really found this beautiful and thought of giving it a share.I won't spoil the essence of this problem, but definitely expecting some nice approaches and solutions in the comment.

  • Vote: I like it
  • +12
  • Vote: I do not like it

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

Auto comment: topic has been updated by cryo_coder123 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

dp[i] = the longest subsequence from the first i element which has the condition (xor = k) and the last element in the subsequence is arr[i]. then dp[i] = dp[last (arr[i] ^ k)] + 1, and you can save what is the last x.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

First if k=0 we can see the answer is the frequency of the element which occurs maximum number of times in the array. Else we can do the following:

First keep track of vector of positions of each element in the array. It is easy to see that the required subsequence must be of the form [x, x^k, x, x^k.....] for some 1<=x<=10^6. So just brute force for each possible value of x and greedily check the subsequence with maximum length we can obtain by using the vector of positions for x and x^k.

Time complexity: O(10^6) + O(n)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya did the same thing... have a look at my piece of code

    int maxSubsequenceLength(int n,int k,vector<int>arr){
	int maxe=*max_element(arr.begin(),arr.end());
	vector<int>all_pos[maxe+1];
	for(int i=0;i<n;i++)
		all_pos[arr[i]].pb(i);
	vector<bool>vis(n+1,false);
	unordered_map<int,bool>hash;
	for(int i=0;i<n;i++)
		hash[arr[i]]=true;
	int ans=1;
	for(int i=0;i<n;i++){
		if(hash[k^arr[i]]==true and vis[i]==false){
			int a=arr[i];
			int b=k^arr[i];
			int count=1;
			bool first=false;
			int pos=i;
			vis[pos]=true;
			while(1){
				if(first){
					auto it=upper_bound(all_pos[a].begin(),all_pos[a].end(),pos);
					if(it==all_pos[a].end()){
						break;
					}
					count++;
					pos=all_pos[a][it-all_pos[a].begin()];
					vis[pos]=true;
					first=false;
				}
				else{
					auto it=upper_bound(all_pos[b].begin(),all_pos[b].end(),pos);
					if(it==all_pos[b].end()){
						break;
					}
					count++;
					pos=all_pos[b][it-all_pos[b].begin()];
					vis[pos]=true;
					first=true;
				}
			}
			ans=max(ans,count);
		}
	}
	return ans;
}
    → Reply