## PROBLEM LINK:

**Author:** Hruday Pabbisetty

**Tester:** Triveni Mahatha

**Editorialist:** Adarsh Kumar

## DIFFICULTY:

Easy-Medium

## PREREQUISITES:

Prefix Sum

## PROBLEM:

You are given an array with N elements. You need to answer Q queries. In each query, you are given two parameters L and R, and you have to find the smallest integer X such that 0 \le X < 2^{31} and the value of \sum \limits_{i=L}^R (A[i]\text{ xor }X) is maximum possible.

## EXPLANATION:

Lets focus on the binary representation of each A[i]'s and X. You can observe that each bit are independent, i.e. you can solve the same problem by iterating over each bit. Basically, for each bit you can reduce the problem to simpler one.

Given a **binary array** P of length N. And in each query, you need to find minimum X where 0 \le X \le 1 and the value of G(L,R) = \sum\limits_{i=L}^R (P[i]\text{ xor }X) is maximum possible. Lets see, if we take X = 0, value of G(L,R) will be equal to number of occurences of 1 in range (L,R). If we take X=1, value of G(L,R) will be equal to number of occurences of 0 in range (L,R). Hence, we can conclude that if the number of occurences of 1 is greater than or equal to number of occurences of 0 in range we will take X as 0 else we will take X as 1.

For each query, we just need to answer number of bits that are 1 at j^{th} bit in the range (L,R) for all 0 \le j < 31. For doing the same we will maintain prefix sum for each of the bit position. The pre-processing part can be done in O(N.log(MAX)). We can answer each of the query in O(log(MAX)) now, i.e. O(1) for each of the bit position. For more implementation details, you can have a look at attached solutions.

## Time Complexity:

O((Q+N).log(MAX))