[Problem Link](https://codeforces.net/problemset/problem/1322/B)↵
~~~~~↵
// package Quarantine;↵
↵
import java.io.*;↵
import java.util.Arrays;↵
import java.util.StringTokenizer;↵
↵
public class Present {↵
static class Reader↵
{↵
final private int BUFFER_SIZE = 1 << 16;↵
private DataInputStream din;↵
private byte[] buffer;↵
private int bufferPointer, bytesRead;↵
↵
public Reader()↵
{↵
din = new DataInputStream(System.in);↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public Reader(String file_name) throws IOException↵
{↵
din = new DataInputStream(new FileInputStream(file_name));↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public String readLine() throws IOException↵
{↵
byte[] buf = new byte[64]; // line length↵
int cnt = 0, c;↵
while ((c = read()) != -1)↵
{↵
if (c == '\n')↵
break;↵
buf[cnt++] = (byte) c;↵
}↵
return new String(buf, 0, cnt);↵
}↵
↵
public int nextInt() throws IOException↵
{↵
int ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do↵
{↵
ret = ret * 10 + c - '0';↵
} while ((c = read()) >= '0' && c <= '9');↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public long nextLong() throws IOException↵
{↵
long ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public double nextDouble() throws IOException↵
{↵
double ret = 0, div = 1;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
↵
if (c == '.')↵
{↵
while ((c = read()) >= '0' && c <= '9')↵
{↵
ret += (c - '0') / (div *= 10);↵
}↵
}↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
private void fillBuffer() throws IOException↵
{↵
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);↵
if (bytesRead == -1)↵
buffer[0] = -1;↵
}↵
↵
private byte read() throws IOException↵
{↵
if (bufferPointer == bytesRead)↵
fillBuffer();↵
return buffer[bufferPointer++];↵
}↵
↵
public void close() throws IOException↵
{↵
if (din == null)↵
return;↵
din.close();↵
}↵
}↵
public static void main(String[] args)throws IOException {↵
Reader s=new Reader();↵
int n=s.nextInt();↵
int a[]=new int[n+1];↵
for(int i=1;i<=n;i++){↵
a[i]=s.nextInt();↵
}↵
int ans=0;↵
for(int i=0;i<=25;i++){↵
int b[]=getArray(a,i);↵
Arrays.sort(b);↵
long count=getCount(b,n,i);↵
if(count%2!=0){↵
ans|=1<<i;↵
}↵
}↵
System.out.println(ans);↵
}↵
public static int[] getArray(int a[],int k){↵
int b[]=new int[a.length];↵
int t=1<<(k+1);↵
for(int i=1;i<a.length;i++){↵
b[i]=a[i]%t;↵
}↵
return b;↵
}↵
public static long getCount(int b[],int n,int k){↵
long ans=0;↵
int left1=1<<k;↵
int right1=1<<(k+1);↵
int left2=(1 << k) + (1 << (k + 1));↵
int right2=1 << (k + 2) - 1;↵
int x=n+1;↵
for(int i=1;i<=n;i++){↵
int rc=getInd(b,i,n,left1);↵
if(rc==x){↵
continue;↵
}↵
int lc=getInd(b,i,n,right1);↵
ans+=lc-rc;↵
if(k!=0) {↵
rc = getInd(b, i, n, left2);↵
if(rc==x){↵
continue;↵
}↵
lc = getInd(b, i, n, right2);↵
ans += lc - rc;↵
}↵
}↵
return ans;↵
}↵
public static int getInd(int a[],int ind,int n,int reqd){↵
int num=a[ind];↵
int low=ind+1;↵
int high=n;↵
int ans=n+1;↵
while(low<=high){↵
int mid=(low+high)/2;↵
if(a[mid]+num>=reqd){↵
ans=mid;↵
high=mid-1;↵
}↵
else{↵
low=mid+1;↵
}↵
}↵
return ans;↵
}↵
}↵
↵
~~~~~↵
↵
~~~~~↵
↵
import java.util.Arrays;↵
import java.util.StringTokenizer;↵
↵
public class Present {↵
static class Reader↵
{↵
final private int BUFFER_SIZE = 1 << 16;↵
private DataInputStream din;↵
private byte[] buffer;↵
private int bufferPointer, bytesRead;↵
↵
public Reader()↵
{↵
din = new DataInputStream(System.in);↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public Reader(String file_name) throws IOException↵
{↵
din = new DataInputStream(new FileInputStream(file_name));↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public String readLine() throws IOException↵
{↵
byte[] buf = new byte[64]; // line length↵
int cnt = 0, c;↵
while ((c = read()) != -1)↵
{↵
if (c == '\n')↵
break;↵
buf[cnt++] = (byte) c;↵
}↵
return new String(buf, 0, cnt);↵
}↵
↵
public int nextInt() throws IOException↵
{↵
int ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do↵
{↵
ret = ret * 10 + c - '0';↵
} while ((c = read()) >= '0' && c <= '9');↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public long nextLong() throws IOException↵
{↵
long ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public double nextDouble() throws IOException↵
{↵
double ret = 0, div = 1;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
↵
if (c == '.')↵
{↵
while ((c = read()) >= '0' && c <= '9')↵
{↵
ret += (c - '0') / (div *= 10);↵
}↵
}↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
private void fillBuffer() throws IOException↵
{↵
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);↵
if (bytesRead == -1)↵
buffer[0] = -1;↵
}↵
↵
private byte read() throws IOException↵
{↵
if (bufferPointer == bytesRead)↵
fillBuffer();↵
return buffer[bufferPointer++];↵
}↵
↵
public void close() throws IOException↵
{↵
if (din == null)↵
return;↵
din.close();↵
}↵
}↵
public static void main(String[] args)throws IOException {↵
Reader s=new Reader();↵
int n=s.nextInt();↵
int a[]=new int[n+1];↵
for(int i=1;i<=n;i++){↵
a[i]=s.nextInt();↵
}↵
int ans=0;↵
for(int i=0;i<=25;i++){↵
int b[]=getArray(a,i);↵
Arrays.sort(b);↵
long count=getCount(b,n,i);↵
if(count%2!=0){↵
ans|=1<<i;↵
}↵
}↵
System.out.println(ans);↵
}↵
public static int[] getArray(int a[],int k){↵
int b[]=new int[a.length];↵
int t=1<<(k+1);↵
for(int i=1;i<a.length;i++){↵
b[i]=a[i]%t;↵
}↵
return b;↵
}↵
public static long getCount(int b[],int n,int k){↵
long ans=0;↵
int left1=1<<k;↵
int right1=1<<(k+1);↵
int left2=(1 << k) + (1 << (k + 1));↵
int right2=1 << (k + 2) - 1;↵
int x=n+1;↵
for(int i=1;i<=n;i++){↵
int rc=getInd(b,i,n,left1);↵
if(rc==x){↵
continue;↵
}↵
int lc=getInd(b,i,n,right1);↵
ans+=lc-rc;↵
if(k!=0) {↵
rc = getInd(b, i, n, left2);↵
if(rc==x){↵
continue;↵
}↵
lc = getInd(b, i, n, right2);↵
ans += lc - rc;↵
}↵
}↵
return ans;↵
}↵
public static int getInd(int a[],int ind,int n,int reqd){↵
int num=a[ind];↵
int low=ind+1;↵
int high=n;↵
int ans=n+1;↵
while(low<=high){↵
int mid=(low+high)/2;↵
if(a[mid]+num>=reqd){↵
ans=mid;↵
}↵
else{↵
low=mid+1;↵
}↵
}↵
return ans;↵
}↵
}↵
↵
~~~~~↵
↵
