You are given a sequence A1,A2,…,AN and you have to perform the following operation exactly X times: Choose two integers i and j such that 1≤i<j≤N .Choose a non-negative integer p(could be 0) .Change Ai to Ai^pow(2,p), and change Aj to Aj^pow(2,p), where ^ denotes bitwise XOR.
Find the lexicographically smallest sequence which can be obtained by performing this operation exactly X times.
Let us say the sequence is (2,2,3) . Consider the following three operations:
Choose i=1, j=2 and p=1. Then, A1 changes from 2 to 2@pow(2,1)=0 and similarly, A2 changes from 2 to 2^pow(2,1)=0. Now the sequence is (0,0,3) .
Next, choose i=1 , j=2 and p=1. Then, A1 changes to 0^pow(2,1)=2 and A2 changes to 0^pow(2,1)=2. The sequence is (2,2,3) . Next, again choose i=1 , j=2 and p=1. Then, A1 changes to 2^pow(2,1)=0 and A2 changes to 2^pow(2,1)=0. The sequence is (0,0,3) again.
hence after 3 operation (0,0,3) is the smallest lexicographically sequence we can get.
1≤T≤10
2≤N≤pow(10,5)
1≤X≤pow(10,9)
1≤Ai≤pow(10,9)
for each valid i
What I have tried:
Okay I have come up with a greedy approach. taking the highest active 1 in the first number note its position and then doing (1<<p) and then xoring the numbers which have 1 activated in this place by iterating to the rest numbers till my x becomes zero.
But obviously by looking at the constraints we can see that we need a better algo as it would give a tle.