Maximum XOR

Given an array of positive integers, find 2 elements such that their xor: a ^ b is maximum.

Let us take an example to know what to be implemented.

If the array elements are: 12, 15, 9.

We need to find out the maximum xor value possible from these elements by taking any two integers from the given array.

Possible xor's are:

12^15=3.

12^9=5.

15^9=6.

In the above results, the maximum xor value is 6, so the answer is 6.

Let us take another example to understand in detail.

If the array elements are 13 11 35 3 32.

If we apply xor for all possible combinations, we get a maximum xor value of 46.

Now, we need to implement the code for this, i.e., to find the maximum xor value by using any two values from the array.

CODE:

Output:

Explanation:

Input Reading:

The program starts by reading an integer t from the standard input. This represents the number of test cases.

Test Case Loop:

The program then enters a loop that iterates t times, representing each test case.

Array Initialization:

Inside the loop, a long, long integer n is read from the standard input, representing the size of an array.

Array Population:

A vector named vec is declared to store n integers.

The program then enters another loop to read n integers and populate the vector.

Bitwise XOR Operation:

The program initializes an integer variable and sets it to 0.

It then uses nested loops to iterate through all pairs of elements in the vector (vec), performing a bitwise XOR operation (^) on each pair.

Finding Maximum XOR:

The result of the XOR operation is compared with the current value of ans, and the maximum value is stored in ans.

This process continues until all pairs of elements in the vector have been considered.

Output:

Finally, the maximum XOR value (ans) for the current test case is printed to the standard output.

Let us discuss the time and space complexity:

Time Complexity:

Input Reading:

Reading the integer t takes constant time.

Test Case Loop:

The test case loop runs t times, where t is the number of test cases.

Array Population:

The array/vector is populated with n elements, where n is the array size for each test case.

Bitwise XOR Operation:

The nested loops iterate through all pairs of elements in the array/vector.

This results in a time complexity of O(n^2), where n is the array size for each test case.

Output:

Printing the result takes constant time.

The nested loops dominate the overall time complexity, resulting in O(t * n^2), where t is the number of test cases, and n is the size of the array for each test case.

Space Complexity:

Input Variables:

The input variables, including integer t and long integer n, determine the space complexity.

These variables take constant space.

Vector vec:

The vector vec is used to store the array elements.

Its space complexity is O(n), where n is the array size for each test case.

Other Variables:

Other variables, such as ans, are scalar and take constant space.

The overall space complexity is O(n), where n is the maximum array size for any test case.

In summary:

Time Complexity: O(t * n^2)

Space Complexity: O(n)