MINMXOR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: rahularya1
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an array A, you’re allowed to remove at most one element from it.
Find the minimum possible value of the XOR of the remaining elements.

EXPLANATION:

The simplest way to solve this problem is to utilize two properties of XOR:

  • XOR is an involution, which is a fancy way of saying x\oplus x = 0 for all x.
  • XOR is associative and commutative, meaning you can move integers around in an expression and their XOR doesn’t change.

One way to use these properties is, if you have the XOR of several integers and want to remove one of them, you can do that by just XOR-ing with that integer!
For example, if we have the N integers [A_1, A_2, \ldots, A_N] and we want to find the XOR of everything except A_i, we can do it as:

(A_1 \oplus A_2\oplus \ldots \oplus A_{i-1} \oplus A_{i+1} \oplus \ldots A_N) \\ = (A_1 \oplus A_2\oplus \ldots \oplus A_{i-1} \oplus A_{i+1} \oplus \ldots A_N) \oplus 0 \\ = (A_1 \oplus A_2\oplus \ldots \oplus A_{i-1} \oplus A_{i+1} \oplus \ldots A_N) \oplus (A_i \oplus A_i) \\ = (A_1 \oplus A_2\oplus \ldots \oplus A_{i-1} \oplus {\color{red}{A_i}} \oplus A_{i+1} \oplus \ldots A_N) \oplus A_i \ \ \ \text{(moving one } A_i \text{ inside)}\\

Notice that the left part of that expression is just the XOR of all the elements of A!

So, to compute the XOR of everything other than A_i, we:

  • First compute S = A_1\oplus A_2\oplus \ldots \oplus A_N.
  • Then compute S\oplus A_i.

Now it’s easy to see that we can do this quickly for each A_i, since S is a constant and so only needs to be computed once.

The final answer is the minimum of S (to account for the case when no elements are removed), and the minimum value among all the (S\oplus A_i) values.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    allxor = 0
    for x in a: allxor ^= x
    ans = allxor
    for x in a: ans = min(ans, allxor ^ x)
    print(ans)
2

But Question me minimum xor find krna hai and iss editorial ke problem statement me maximum xor hai

3

Though I solved this problem like this, I’m not able to see what’s wrong in this one

``import java.util.;
import java.lang.;
import java.io.*;
class Codechef
{
public static void main (String args) throws java.lang.Exception
{
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while(t–>0)
{
int x = s.nextInt();
int arr = new int;
int sum=0;
int aux = new int;
for(int i =0; i<x ;i++)
{
arr[i]=s.nextInt();
sum^=arr[i];
}
int prefix = 0;
int postfix = 0;

    for (int i = 0; i < x; i++) {
        aux[i] = prefix;
        prefix ^= arr[i];
    }

    for (int i = x - 1; i >= 0; i--) {
        aux[i] ^= postfix;
        postfix ^= arr[i];
    }
         if(sum==0)
      System.out.println(sum);
      else
      {
         Arrays.sort(aux);
        System.out.println(aux[0]);
         
      }
      
}
}

}``

Please tell me what’s wrong.

4

Typo, fixed now (the solution doesn’t change at all).

5

You forgot to consider the case when the xor of everything is the minimum.

1
2
2 3

The answer is 1.

6

Got it now. Thanks!!