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.
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
def sansaXor(arr):
if len(arr) % 2 == 0: # cancels if even
return 0
# element at even pos exists odd times in sublists -> iterate by 2
# element at odd pos exists even times in subslist -> cancels
return getXor(arr)
def getXor(lst):
ans = 0
for i in range(0, len(lst), 2):
ans ^= lst[i]
return ans
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sansa and XOR
You are viewing a single comment's thread. Return to all comments →
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