Hey all,
I was trying this problem Big Number Array on Hackerearth. I tried simple brute force but only one test case passed.
I also looked at the editorial but they only published the code and not the explanation.
It will be very helpful if someone could explain the approach.
Thanks in advance!
Flipping the l-th bit to r-th bit in a number is same as XORing that number with a number having 1s only in positions from ‘l’ to ‘r’. Let’s denote the number whose first ‘k’ bits are 1s and the remaining are 0s as Xk . So, if you flip the bits from position ‘l’ to position ‘r’ in a number ‘A’, the resulting number will be equal to A XOR Xl-1 XOR Xr. But, since l,r are big, it is impossible to actually XOR with those numbers.
So, we will use some random numbers to take the place of each Xk. Suppose that we will assign each Xk a value that is uniformly randomly selected from the range [0,2h-1]. Each update will be a range XOR operation now. However, there is a problem with this approach, because there is a chance that two numbers might end up getting the same value (after XORing), even though the bits present in them are different. It is impossible to completely eliminate this, but we can decrease the probability of this happening, to a point where its almost negligible. This can be done by choosing a suitably large value for the range of random numbers.
If the numbers are uniformly randomly chosen from the range [0,2h-1], a sequence of XOR operations will give us a result in the same range as well. Irrespective of the length of the sequence, the probability of the result being equal to any number in the range [0,2h-1] is same (why?). In the worst case, all the ‘N’ numbers will be different, and we need to minimise the probability that the value we get after performing XOR operations on any two numbers out of them are equal. If you set h=64, and N=10^5, the probability of getting a random collision (two numbers with same value) will be less than 10-9 ( https://en.wikipedia.org/wiki/Birthday_attack ).