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.
Sansa and XOR
Sansa and XOR
Sort by
recency
|
181 Discussions
|
Please Login in order to post a comment
To undestand the problem I recommend to try to resolve it using pen and paper.
At first I did three functions: one for getting the sublists, one for getting the XOR results, and the main one. It was clear that there are some math tricks you need to take into account in order to pass the time limit tests. Below I explain what are those, since the vast majority of solutions do not.
If the lenght of the arr is even the result will always cancel out. For example 2 XOR 2 is 0, 1 XOR 2 XOR 3 XOR 4 is 0.
When you get all the sublists you will notice that an element at even position exists odd times in all of the sublists and viceversa, an element at odd position exists even times in all of the subslists.
For example: [1,2,3] has the following sublists = [1],[1,2],[1,2,3],[2],[2,3],[3], the one appears 3 times, the 2 appears 4 times and the 3 appears 3 times.
This means that the elements that are on odd positions will cancel out, and we only need to take into consideration the ones that are on even positions, thus we only need to XOR the elements on the array stepping by 2.
code
Python 3 solution:
java easy solution
When xor same elements eliminate 2 ^ 3 ^ 2 ^ 3 ^ 6 = 6 First write examples and try solve step by step and you will see the big picture.