Xor Of Sum Of All Pairs

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given an array of integers.
2. You have to find the XOR of sum of all pairs in the array.
Input Format
A number N
arr1
arr2..
N numbers
Output Format
Check the sample ouput and question video.
Question Video
Constraints
1 <= N <= 10^9
1 <= arr[i] <= 10^9
Sample Input
5
1
5
2
1
2
Sample Output
10


  • Editorial

    The problem here deals with finding the XOR of the sum of all pairs of the given array.

    Let us consider the following example:

    Input array: [ a, b, c, d ]

    Now here we wish to have the XOR of all the pairs. One way to solve this is to go for nested looping wherein we will be forming every pair and then performing XOR with the result. The time complexity, in this case, would be O(n2), but we wish to optimize the time complexity to O(n).

    If we carefully observe then we can notice that (a+b) is repeating as (b+a) similarly (a+c) is repeating as (c+a) and so on. Now we can see that only {2*a}, {2*b}, {2*c} and {2*d} are  not repeating. So taking XOR of all the pairs is equal to taking XOR of {2*a}, {2*b}, {2*c} and {2*d}.

    Also,

    { ( 2 * a ) ^ ( 2 * b ) ^ ( 2 * c ) ^ ( 2 * d ) } = 2 * ( a ^ b ^ c ^ d )

    Therefore we have successfully converted our O(n2) solution to O(n) solution by mere checking of repeatitive pattern.

    Time Complexity: O(n)

    The time complexity for the function is linear as we are traversing on every element once.

    Space Complexity: O(1)

    The space complexity for the function is constant.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name