papa-ka-para's blog

How to solve this problem ?
By papa-ka-para, history, 20 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

»
20 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
→ Reply