XOR of Array Elements Except Itself in Java

It is a problem frequently asked in interviews of top IT companies like Google, Amazon, TCS, Accenture, etc. By solving the problem, one wants to check the logical ability, critical thinking, and problem-solving skill of the interviewee. So, in this section, we are going to discuss XOR of array elements except itself in Java with different approaches and logic. Also, we will create Java programs for the same.

Problem Statement

We have given an array that contains only non-negative elements. The task is to create another array (say output[]) such that output[i] contains XOR of all the elements of the input array except input[i]. The following examples illustrates the same.

Let's understand it through examples.

Example 1:

Input: int input[] = {4, 7, 9, 3, 2, 5, 6}

Output: output[] = {12, 15, 1, 11, 10, 13, 14}

Explanation: If we exclude the current element and apply the XOR operation on rest of the elements, we get the mentioned output. Observe the following.

output[0] = 7 ^ 9 ^ 3 ^ 2 ^ 5 ^ 6 = 12

output[1] = 4 ^ 9 ^ 3 ^ 2 ^ 5 ^ 6 = 15

output[2] = 4 ^ 7 ^ 3 ^ 2 ^ 5 ^ 6 = 1

output[3] = 4 ^ 7 ^ 9 ^ 2 ^ 5 ^ 6 = 11

output[4] = 4 ^ 7 ^ 9 ^ 3 ^ 5 ^ 6 = 10

output[5] = 4 ^ 7 ^ 9 ^ 3 ^ 2 ^ 6 = 13

output[6] = 4 ^ 7 ^ 9 ^ 3 ^ 2 ^ 5 = 14

Example 2:

Input: int input[] = {0, 6, 2, 9}

Output: output[] = {13, 11, 15, 4}

Explanation:

output[0] = 6 ^ 2 ^ 9 = 13

output[1] = 0 ^ 2 ^ 9 = 11

output[2] = 0 ^ 6 ^ 9 = 15

output[3] = 0 ^ 6 ^ 2 = 4

Solution to the Problem

Naive Approach

In this approach, we will use a nested for loop for computing the XOR of all the elements except itself.

FileName: XorArrElements.java

Output:

For the input array: 
4 7 9 3 2 5 6 
The output array is: 
12 15 1 11 10 13 14 

For the input array: 
0 6 2 9 
The output array is: 
13 11 15 4

Complexity Analysis: The program uses the nested for-loop. Hence, the time complexity of the above program is O(n²), where n is the total number of elements present in the input array. The program is not using any extra space. Thus, the space complexity of the program is constant, i.e., O(1).

The time complexity of the program can be reduced further. The following approach shows the same.

Computing XOR of All The Elements

We know that the XOR of the two numbers is always zero if both numbers are equal. Thus, we can compute the XOR of all the elements, and to exclude any element, do the XOR of all the elements with that element. Let's understand it with the help of an example.

int arr[] = {a1, a2, a3, a4, a5, a6}, size = 6

Thus, output[0] = (a1 ^ a2 ^ a3 ^ a4 ^ a5 ^ a6) ^ a1,

We know that the XOR operation is commutative. Therefore, we can group a1 together

output[0] = (a1 ^ a1 ^ a2 ^ a3 ^ a4 ^ a5 ^ a6) = 0 ^ a2 ^ a3 ^ a4 ^ a5 ^ a6 (as a1 ^ a1 = 0)

which is nothing but the XOR of all the elements except the element itself. The following program used the same concept.

FileName: XorArrElements1.java

Output:

For the input array: 
4 7 9 3 2 5 6 
The output array is: 
12 15 1 11 10 13 14 

For the input array: 
0 6 2 9 
The output array is: 
13 11 15 4

Complexity Analysis: The time complexity of the program is O(n), where n is the total number of elements present in the input array. The space complexity of the program is the same as the above.