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.
If I look at the discussions, here a couple of hints that might get you on the right track and improve your learning:
Trying to create all subsets, XORing their elements, and then adding everything up will only work for very small n (note that there are 2^n-1 subsets, which is ridiculously large for every n larger than 20 (for 20 it would be roughly 1m subsets))
You need to look at the individual bits, as XOR is a bitwise operation. Start with a small sample (e.g. as small as binary 0 and 1) and check out how many of the subsets yield a 1 as result at bit position 0 ({}->0 {0}->0 {1}->1 {0,1}->1) [I know, the description says to ignore the empty subset, but that is completely irrelevant and actually makes understanding things harder]. Now think about what happens when you have also a bit at position 1: You still have above subsets, plus copies with the new elements included - what does this do to the number of 1 bits at position 0, and what about position 1?
Look at in which situations you have 1 bits at all (how many you calculate according to your findings from above paragraph), and you will quickly understand why ORing the inputs is helpful
The rest becomes about how to efficiently calculate terms like (2^(n-1))%b where b = 1000000007. Just two comments:
(a*b*c)%m is identical to (((a*b)%m)*c)%m; if a,b,c and m are of the same order of magnitude, it is much more efficient to do the "modulo reduction" after every multiplication, rather than calculating the product into a BigInt and reduce then;
Calculating 2^n by doing n multiplications by 2 (even if these are shifts) is ridiculously slow for large n - come on guys, we know how to do better (hint, you can do it in O(log n) steps, i.e. at most 17 steps for our n=10^5 situation)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Xoring Ninja
You are viewing a single comment's thread. Return to all comments →
If I look at the discussions, here a couple of hints that might get you on the right track and improve your learning:
The rest becomes about how to efficiently calculate terms like (2^(n-1))%b where b = 1000000007. Just two comments: