Before you move any further, it is advised that you give this problem a fair try.
Let's jump to the problem.

Understanding the problem:

In this problem you are given an array of integers.

All you need to do is to find the XOR of the sum of all pairs in the array in linear time.

Sample Input: 5
1 5 2 1 2

Sample Output: 10

How?

Well the answer would be = (1+1)^(1+5)^(1+2)^(1+1)^(1+2)^(5+1)^(5+5)^ (5+2)^(5+1)^(5+2)^ (2+1)^(2+5)^(2+2)^(2+1)^(2+2)^(1+1)^(1+5)^(1+2)^
(1+1)^(1+2) ^ (2+1)^(2+5)^(2+2)^(2+1)^(2+2)

which will eventually yield 10.

For more clarity of the question, watch this part of the video.

Approach:

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

Let us consider another 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.

We can also see that only (a + a), (b + b), (c + c) and (d + d) are not repeating.

So taking XOR of all the pairs is equal to taking XOR of (a + a), (b + b),
(c + c) and (d + d) as the repeating pairs like (a + b) and (b + a), (a + c) and (c + a) and so on cancel out.

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

Therefore we have successfully converted our O(n^2) solution to O(n) solution by mere checking of repetitive patterns.

Let's try to code this change!

Well, this was quite easy. Wasn't it?

For more clarity of this part, watch this part of the video.

We can reduce this further by using another property of the XOR operator.

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

Why does this property hold?

This holds because (2*a) add a zero to the right in the binary of a. Similar happens to b, c and d. And when we perform XOR among these doubled values, the rightmost zeros of each value yields zero only at the right most bit of the answer's binary.

And if we first do the XOR of all the elements and then double the answer, this means a zero has been introduced in the right of the answer's binary.

Let's try to code this change!

Yes! Like that.

For more clarity of this part, watch this part of the video.

Complexities:

Time Complexity: O(n)

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

Space Complexity: O(1)

The space complexity for the function is constant.

Complete Code:

import java.io.*;
import java.util.*;
public class Main {
public static int solution(int[] arr){
int ans = 0;
for(int i = 0 ; i < arr.length; i++){
ans ^= (2 * arr[i]);
}
return ans;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for(int i = 0 ; i < n; i++){
arr[i] = scn.nextInt();
}
System.out.println(solution(arr));
}
}

java;
true";

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!
Happy Coding!