KS1 - Guddu and his Mother

That’s because you have missed out the condition for 0 i think.
Whenever xor_tn = 0 you have to add ans += i as well along with ans+= i-list.lastindexof(xor_tn).
Check your code for example 5 2 7 , does it give 2 as answer ?
@as_max_rider

format code ////////

Could you please share the pages you read for optimization with hashmaps

for(i = 1, i < k, i++) {
    			if(i > 1)
	        			temp += (vv[i] - vv[i-1] - 1) * (i - 1) + (i - 2);
    			cnt += (vv[i] - vv[0] - 1) + temp;
    		}

Can you please help me with this code ??? (._.!) Didn’t get logic for this…

To be honest I’ve complicated a simple thing
Check this simpler approach instead

Very well documented. Thanks!

1 Like

Hello, I managed to understand the logic behind it thanks to you all. However, I still have 2 testcases that give W/A in Java ( I just started learning it 2 weeks ago). If I had to do it in C++, I would’ve used a STL vector, but due to the fact that I didn’t find anything like this in Java, I used a “HashMap”. Help would be much appreciated. Thanks in advance!
https://www.codechef.com/viewsolution/25925223

How counting distance between pairs helps us in counting triplets ?
What if there’s no common XOR in the prefix XOR array ?
What if when XOR in prefix XOR array comes out to be zero ?

Try to understand this code :
If ‘k’ has already appeared in xor array more than once, add its contribution to the sum.
check complete code

1). For example consider a triplet that we have got from a certain sequence of numbers is (i,j,k) = (1,6,6).
Then the final answer(triplets) also includes (1,2,6) , (1,3,6), (1,4,6), (1,5,6). As, you can see now j is varying from i+1 to k. So, if you know the pair (i,k) you can easily calculate the no of triplets by the difference of indices. Formula will be :- k - i

2). If there’s no common XOR in the prefix XOR array then the answer (no. of triplets) obviously be zero.
3). When XOR in prefix XOR array comes out to be zero , then you can just add the index of that Zero value in that prefix XOR array to our final answer.

I’m late to the party :smile:
I’ll explain my approaches :—

  1. PURE BRUTE FORCE :-- Includes three for loops, the very basic approach. Link : 20 PTS.
  2. OPTIMIZED A BIT :-- Includes two for loops :slight_smile: Link: 50 PTS.
    Sadly :neutral_face:, I wasn’t able to do the problem before the contest ends as i was trying to do it using hashing/sorting related approach but didn’t worked out my way.Half - an hour before the contest ends, I’ve noticed that there is something a pattern or formula or whatever needed to calculate the count sum for a PREFIX XOR VALUE that was repeated.
    But, here we go
    3). AC CODE Link : 100 PTS.
    BTW formula is: For index i, in which a XOR value that occurs after its first occurrence
    is i*(count of that xor value not including its own value) - (sum of all the positions of that prefix XOR value occurring before this Prefix XOR VALUE at i’th index).
    If you have any problem with my explanation please check out my codes.
    Approaches was ordered according to sub-tasks :smile:
  3. Passes only Sub-task1 ----- O(N^3) Approach
  4. Passes both Sub-task1 & Sub-task2 ------ O(N^2) Approach
    3)Passes all the Sub-tasks [1,2,3] ------- O(N) Approach.
    BTW, PREFIX XOR VALUE = 0, a case that we just need to add the index of it to our final answer(count).

@duddumahesh
Link to My Solution : CodeChef: Practical coding for everyone
Can you help me identifying where am I going wrong please ?

I don’t know much about java but i guess you were not adding the first element of prefix array to the map.

for input
1
10
1 2 3 4 5 5 4 3 2 1

Your code gives output : 37
but the correct output is : 47

I just did it in C++ with a STL vector and it works without a problem. Where is the difference between these 2 solutions ?
CodeChef: Practical coding for everyone ( C++ )(CodeChef: Practical coding for everyone) ( JAVA )

Here’s the working code AC 100 PTS.
Things that I’ve Changed :–

  1. Included the very first element of the prefix array i.e. preXOR[0] in the map.
  2. Changed the variable type to long for variables like ans, size…etc
    That’s it.
    Thanks for sharing your solution with hash map.

Thanks buddy!
I really appreciate your help & support.
Kudos to codechef for providing such a platform!

1 Like

Consider checking out - Counting the number of triplets in an array - Guddu and his mother - Part 1 - YouTube for O(n) solution

Do you have any YouTube link for problem CHGORAM from Aug19 long challenge ?

Just 1 last thing … I’m not able to understand the test case where prefix XOR array has zero within it.
Then firstly I’m calculating all the pairs & their distance formed for 0 in the prefix XOR array --> adding to ans . And then I’m adding directly the index to the ans as well.
Q1.) Why is that so ?

As per the last line of code
ans = ans - (size-1)*size/2 // Just because we have to calculate the triplets for sub-array of length n-1 we need to subtract our ans(count of triplets) from the total no. of pairs formed by the sub-arrays.
Q2.) Is that right ? If yes then it means that calculating distance between the pairs formed in prefix XOR array doesn’t give the count of triplets , then what does it returns ?