Блог пользователя papa-ka-para

Автор papa-ka-para, история, 13 месяцев назад, По-английски

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 ?

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
13 месяцев назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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