Problem link: XORs
Solution:
We will be given some integers. We are asked to output the cumulative xor sum of all possible pair from those integers; where pair (a[i] ^ a[j]) and 1 <= i, j <= n [i, j = index]
Given the array 1 2 2 4 5, we have to perform our operation like below->
For 1, take all possible pairs:
3 ^ 3 ^ 5 ^ 4 ^ 0 ^ 6 ^ 7 ^ 6 ^ 7 ^ 1 = 0
So, how can we solve this? If we try to use bruteforce approach, complexity would be so much and we will surely get TLE in the process.
Let's consider the previous array 1 2 2 4 5, here for 1 we have exactly 4 pairs, for 2(first) we have 3 pairs, for 2(second) we have 2 pairs... for 5 we have no pair. Can you see the pattern here? Well let's talk about it, why the number of pair is important for us.
We know, if we xor an integer odd number of times, it becomes 0 (zero) and for even number of times, it becomes the integer itself. For the 4 pairs of 1, we get the following result by xoring all of the pair for 1 like this: (1^2)^(1^2)^(1^4)^(1^5). We can see, as we have xored odd number of one (1), [1 ^ 1 ^ 1 ^ 1]. We can conclude that it will finally be zero (0). So we don't need this in our calculation. What we need is that the xor of (2^2^4^5). Similarly for 2(first) we get 3 pairs, as we are xoring two 2's, and two is even, so we have to xor 2 with the result. So it will look something like this: 2^(2^4^5).
For second 2, we get (4^5).
For 4, we have one pair (zero xor, as zero is even, we need to xor with 4), Finally we get: (4^5).
For 5, we have no pair, so we don't need to do anything.
I hope now you understand why we need the number of pair. We can get the number of pair simply by (n - index_of_the_element). And for each element, we need the cumulative xor of all the element from index+1 to n of that particular index. We can pre calculate the cumulative xor of all the elements in an array. Remember, we need to pre calculate in reverse order for our purpose.
Solution:
We will be given some integers. We are asked to output the cumulative xor sum of all possible pair from those integers; where pair (a[i] ^ a[j]) and 1 <= i, j <= n [i, j = index]
Given the array 1 2 2 4 5, we have to perform our operation like below->
For 1, take all possible pairs:
- (1, 2) = 1 ^ 2 = 3
- (1, 2) = 1 ^ 2 = 3
- (1, 4) = 1 ^ 4 = 5
- (1, 5) = 1 ^ 5 = 4
- (2, 2) = 2 ^ 2 = 0
- (2, 4) = 2 ^ 4 = 6
- (2, 5) = 2 ^ 5 = 7
- (2, 4) = 2 ^ 4 = 6
- (2, 5) = 2 ^ 5 = 7
- (4, 5) = 4 ^ 5 = 1
3 ^ 3 ^ 5 ^ 4 ^ 0 ^ 6 ^ 7 ^ 6 ^ 7 ^ 1 = 0
So, how can we solve this? If we try to use bruteforce approach, complexity would be so much and we will surely get TLE in the process.
Let's consider the previous array 1 2 2 4 5, here for 1 we have exactly 4 pairs, for 2(first) we have 3 pairs, for 2(second) we have 2 pairs... for 5 we have no pair. Can you see the pattern here? Well let's talk about it, why the number of pair is important for us.
We know, if we xor an integer odd number of times, it becomes 0 (zero) and for even number of times, it becomes the integer itself. For the 4 pairs of 1, we get the following result by xoring all of the pair for 1 like this: (1^2)^(1^2)^(1^4)^(1^5). We can see, as we have xored odd number of one (1), [1 ^ 1 ^ 1 ^ 1]. We can conclude that it will finally be zero (0). So we don't need this in our calculation. What we need is that the xor of (2^2^4^5). Similarly for 2(first) we get 3 pairs, as we are xoring two 2's, and two is even, so we have to xor 2 with the result. So it will look something like this: 2^(2^4^5).
For second 2, we get (4^5).
For 4, we have one pair (zero xor, as zero is even, we need to xor with 4), Finally we get: (4^5).
For 5, we have no pair, so we don't need to do anything.
I hope now you understand why we need the number of pair. We can get the number of pair simply by (n - index_of_the_element). And for each element, we need the cumulative xor of all the element from index+1 to n of that particular index. We can pre calculate the cumulative xor of all the elements in an array. Remember, we need to pre calculate in reverse order for our purpose.
No comments:
Post a Comment