papa-ka-para's blog

By papa-ka-para, history, 12 months ago, In English

we are given 4 integers, where a <= b , c <= d.

We have to find Sum of Xor of all the pairs (i,j) such that ( a <= i <= b , && c <= j <= d )


int sum = 0; for(int i=a ; i <= b; i++) { for(int j = c; j <= d ; j++) { sum += (i ^ j) } } return sum;

How to find this sum optimally ?

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
12 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

For each x calculate the effect of 2^x on the answer.

The problem then becomes 32 "at position i, calculate how many zeros are in a certain interval". After getting the number of 1's and 0's just multiply them together. Then add up all the answers and you're done.

Implementation code