You are given integer array A of size N and Q queries for every query you are given L,R and X
You are required to determine the value of
(Al xor x)+(A(l+1) xor x)+…(Ar xor x)
Pls share approaches
This was asked in oyo coding round
@anon55659401 @ssrivastava990 @guitarlover
Pls help
Think about each bit separately
Hello @akshat_165
Intuition behind the algorithm: For each set bit in X, count of 1’s will be same as count of unsetbits in a range. ( Property of XOR )
Edit : I hope your question is not from an ongoing contest.
This can be solved using bit manipulation. Precompute the number of set bits an in a prefix array.
For each query : L R X
Iterate through the bits of X under the following two conditions :
If ith bit is set in X :
Multiply the next power of 2 with the count of unset bits in ith position in the range [L, R]
If ith bit is unset in X :
Multiply the next power of 2 with the count of set bits in ith position in the range [L, R]
Do work out with an example to clear out everything!
Constraint of X<=10^9
But prefix array ?? Constraint X<=10^9 @guitarlover
Its not from any ongoing contest
Its interview question of oyo
Prefix array will store the frequency of set/unset bits. Array of size 32 will be good.
I’ll leave behind some things that you need to figure out yourself (^_^)
countOfSetBits and countOfUnsetBits can be obtained in O(1) time using the prefix array. I reccomend you to get comfortable with prefix array before approaching this problem.
A = [ 7, 4, 3, 1, 5 ]
L = 2
R = 4
X = 6
Binary Representation of X : 000…00110
nextPowerOfTwo = 1
answer = 0
Lets iterate through each bit :
0th position is unset in X :
answer = answer + (nextPowerOfTwo * countOfSetBits )
answer => 0 + ( 1 * 2) = 2
nextPowerOfTwo = nextPowerOfTwo * 2
1st position is set in X :
answer = answer + (nextPowerOfTwo * countOfUnsetBits )
answer => 2 + ( 2 * 2) = 6
nextPowerOfTwo = nextPowerOfTwo * 2
2nd position is set in X :
answer = answer + (nextPowerOfTwo * countOfUnsetBits )
answer => 6 + ( 4 * 2) = 14
After this, all the positons are unset and hence the maximum value is 14
@akshat_165
I don’t want to be rude, but in competitive programming you can ask for hints and for clarifications, but you also have to use an example to understand. We can’t spoon feed you with examples too. In a competition, no one will come to help you even with hints, so try taking this first step.
Scratch your head a bit and you’ll get your answer. Give some time to the problem carefully understand from the very basic 
i mean almost same 
What I found out :
for every set bit in x, find the number of corresponding unset bits in present among all the numbers between L to R and for all unset bits in x, find the number of elements having the corresponding element set. Each of these counts can be pre-computed earlier and prefix sum is needed to find count of number of elements has the ith bit set/unset.
You can refer to my code for implementation details. Let
A simple approach … idk how good it actually is:
Take input a[]
for( each l,r,x)
{
for(each i in a[]){
a[i]=a[i]xor x;}
for(each i in a[]){
prefsum[i]=prefsum[i-1]+a[i];}
ans=prefsum[r]-presum[l]+a[l]
}
Whats the flaw in this method?? Range limit exceed?
We use the property of XOR (1 XOR 0 = 1 and 0 XOR 1 = 1 ) to maximize the answer. Apologies for the confusion there!