We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 19
  3. What Are the Odds?
  4. Discussions

What Are the Odds?

  • iam_ss
     + 4 comments

    I solved it exactly in same manner as explained in editorial. However, I found the implementation (tester's) quite different (tough) than what was explained. However, I implemented it my way which I feel is relatively easier to understand. In case , anyone feels difficult in understanding the editorial's implementation of O(N) . Please refer the below code:

    #include<bits/stdc++.h>
using namespace std;

#define ll long long int

int main()
{
	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
	ll t=1;
	//s(t);
	while(t--){
		ll n;
		cin>>n;
		vector<ll>ar(n+2);
		for(ll i=1;i<=n;i++)cin>>ar[i];

		vector<ll>pref(n+2);
		pref[1]=ar[1];
		for(ll i=2;i<=n;i++)pref[i]=ar[i]^pref[i-1];

		unordered_map<ll,ll> cnt;

		ll suf=0;
		ll ans=0;
		cnt[0]=1;
		for(ll i=n;i>0;i--){
			ans+=cnt[pref[i-1]];
			suf^=ar[i];
			cnt[suf]++;
		}
		cout<<ans<<endl;

	}
}

    Thanks!