XOR of Array Elements Except Itself in Java
A lot of the biggest IT organisations, including The Google, Amazon, TCS, and The Accenture, etc., question about this issue in their interview processes. By addressing the issue, one hopes to assess the interviewee's capacity for logical reasoning, critical analysis, and problem-solving. As a result, in this section we'll cover various methods and rationale for XORing array items other than the self in Java. For the same, we will also develop Java apps. One of the various Bitwise operators in Java is XOR. If two boolean operands are given, the XOR (also known as exclusive OR) returns true. When both of the specified boolean conditions cannot be true at the same time, the XOR operator is most useful. A carrot (^) symbol represents the XOR operator. If there is a difference between the two values, it returns true; otherwise, it returns false. True is represented in binary by 1 and false by 0, with 1 being the default value. The binary operator XOR is determined left to right when used in equations. When used with a String argument, the operator "" is undefinable.
The Problem Statement
We have provided an array with the solely positive and the neutral entries. The goal is to make another array (let's call it output[]) that, with the exception of input[i], has an XOR of every element of the input array. The same is demonstrated by the examples below.
Let's use some examples to the better grasp it.
Input: int input[] = {5, 8, 10, 4, 3, 6, 7}
Output: output[] = {13, 16, 2, 12, 11, 14, 15}
Explanation: Why we receive the output we do is explained by eliminating the remaining part and performing the XOR operation for the other elements. Take note of the following.
output[0] = 8 ^ 10 ^ 4 ^ 3 ^ 6 ^ 7 = 13
output[1] = 5 ^ 10 ^ 4 ^ 3 ^ 6 ^ 7 = 16
output[2] = 5 ^ 8 ^ 4 ^ 3 ^ 6 ^ 7 = 2
output[3] = 5 ^ 8 ^ 10 ^ 3 ^ 6 ^ 7 = 12
output[4] = 5 ^ 8 ^ 10 ^ 4 ^ 6 ^ 7 = 11
output[5] = 5 ^ 8 ^ 10 ^ 4 ^ 3 ^ 7 = 14
output[6] = 5 ^ 8 ^ 10 ^ 4 ^ 3 ^ 6 = 15
Solution to the Problem
By Naive Approach
In this method, determining the XOR of every element other than itself will be done inside a nested for loop. We just cycle through into the array and use the ^ operator to determine the XOR of each of the array's elements. In order to calculate the answer, the following procedures are used:
- Make a variable to hold the result of the array's XOR.
- Use the " operator to discover the XOR within each of the array's elements and the result variable.
- The XOR of each element in the array is then stored in the result variable.
Let the name if the file is XorArrElementsDemo.java
// java program to perform XOR of
// Array Elements Except Itself
public class XorArrElementsDemo
{
// a procedure that computes the xor of all items of the
// array arr[] except the current element.
public int[] findTheXor(int arr[])
{
int cap = arr.len;
int output3[] = new int[cap];
for(int h = 0; h < cap; h++)
{
// with the exception of arr[h] to storing
// this xor for each of the items.
int xor = 0;
for(int l = 0; l < cap; l++)
{
// Leaving off the component arr[h]
if(j != l)
{
xor = xor ^ arr[l];
}
}
// the output array being updated
output3[h] = xor;
} // Here return the output3
return output3;
}
// It is the main method or the driver code
public static void main(String[] argvs)
{
// generating a XorArrElementsDemo object of the desired class
XorArrElementsDemo srj = new XorArrElementsDemo();
int input3[] = {5, 8, 10, 4, 3, 6, 7};
int cap = input3.len;
int output3[] = srj.findTheXor(input);
System.out.println("To the input array: ");
for(int s = 0; s < cap; s++)
{
System.out.print(input3[s] + " ");
}
System.out.println();
System.out.println("This is the output array: ");
for(int s = 0; s < cap; s++)
{
System.out.print(output3[s] + " ");
}
System.out.println("\n" );
// It is the input 2
int input4[] = {1, 7, 3, 10};
// determining the size
size = input4.length;
int output4[] = obj.findTheXor(input4);
System.out.println("To the input array: ");
for(int s = 0; s < cap; s++)
{
System.out.print(input4[s] + " ");
}
System.out.println();
System.out.println("This is the output array: ");
for(int s = 0; s < cap; s++)
{
System.out.print(output4[s] + " ");
}
}
}
Output:
To the input array:
4 8 10 4 3 6 7
This is the output array:
13 16 2 12 11 14 15
To the input array:
1 7 3 10
This is the output array:
14 12 16 5
Analysis of complexity: reveals that the program employs layered for-loops. As a result, the preceding program's time complexity is O(n2)), wherein n is the complete number of elements in the input array. There is no extra space being used by the software. As a result, the program's space complexity, which is constant O(1).
The program's temporal complexity can be lowered even more. The next method demonstrates the same.
Computing the XOR of each element
We are aware that when both numbers are equal, the XOR of them is always 0. In order to eliminate any element, one can estimate the XOR of every element as well as the XOR of each of the components with that element. Let's use an illustration to assist you comprehend it.
size = 6, int arr[] = {b1, b2, b3, b4, b5, b6}
So the Output[0] is therefore equal to (b1 ^ b2 ^ b3 ^ b4 ^ b5 ^ b6) ^ b1
The XOR technique is commutative, as far as we are aware. Consequently, one can group a1 as a whole.
output[0] = (b1 ^ b1 ^ b2 ^ b3 ^ b4 ^ b5 ^ b6) = 0 ^ b2 ^ b3 ^ b4 ^ b5 ^ b6 (as b1 ^ b1 = 0)
This only represents the XOR of all elements other than the element itself. The similar idea was applied in the program that came after.
XorArrElementsDemo.java
public class XorArrElementsDemo
{
// a method that performs the xor operation on all
// items of the array arr[] except the current element.
public int[] findTheXor(int arr[])
{
int capa = arr.len;
int output3[] = new int[cap];
// for keeping track of the elements xor
int xor = 0;
for(int h = 0; h < capa; h++)
{
xor = xor ^ arr[h];
}
for(int l = 0; l < capa; l++)
{
// refreshing the output array while removing
// the arr[k] using XOR for the outpu3[l] element.
output[3] = xor ^ arr[l];
}
return output3;
}
// It is the main method
public static void main(String[] argvs)
{
// generating a XorArrElementsDemo object of the desired class
XorArrElementsDemo srj = new XorArrElementsDemo();
// It is the input 1
int input[] = {5, 8, 10, 4, 3, 6, 7};
// determining the size
int capa = input2.len;
int output3[] = srj.findTheXor(input2);
System.out.println("To the input array: ");
for(int s = 0; s < capa; s++)
{
System.out.print(input2[s] + " ");
}
System.out.println();
System.out.println("This is the output array: ");
for(int s = 0; s < capa; s++)
{
System.out.print(output3[s] + " ");
}
System.out.println("\n" );
// It is the input 2
int input2[] = {1, 7, 3, 10};
// determining the size
capa = input2.len;
int output2[] = srj.findTheXor(input2);
System.out.println("To the input array: ");
for(int s = 0; s < capa; s++)
{
System.out.print(input2[s] + " ");
}
System.out.println();
System.out.println("This is the output array: ");
for(int s = 0; s < capa; s++)
{
System.out.print(output2[s] + " ");
}
}
}
Output:
For the input array:
3 8 10 4 3 6 7
This is the output array:
13 16 2 12 11 14 15
To the input array:
1 7 3 10
This is the output array:
14 12 16 3
Analysis of Complexity: The programme has an O(n) time complexity, while n represents the number of entries inside the input array. The program's spatial complexity is identical to the one mentioned previously.