XOR IT (COOK OFF)

general
1

Can anyone explain the approach of the below question
https://www.codechef.com/COOK113A/problems/XORIT

5 Likes
2

If N is a power of 2, then A=B=-1.
Else, A is the smallest set bit of N. For example, if N = 11010, then A = 10 and B = 11000.

We can then use some math to count for each bit i, the number of N such that the smallest bit of N is i, then we can use more math to find the answer.

https://www.codechef.com/viewsolution/28442534

23 Likes
3

Wow Your code is so clean.
I got the idea but implementation took quite some time :frowning:. Iā€™m so bad at bit manupulationā€¦

1 Like
4

yeah basically the function F(n) is n&(n-1) if (n&(n-1)_!=0 else -1 but how to find sum , please elaborate more :pray:

1 Like
5

This is my algorithm.

  1. Count the sum of all numbers from L to R
  2. Now A is minimum as the rightmost set bit, if N = 101010 then A = 10, if contains only one active bit then its -1. So we just need count of numbers having ith bit as LSB (least significant bit)
    You can do this
    Check number of last 1 bits after right shifting L and R
    And that is reduced to count of odd numbers only
  3. Keep doing this for every bit and reduce them from overall total and you get your answer

My code for reference: Link

6

Sum of B = Sum of (N-A) = Sum of N - Sum of A
Sum of N is easy to find (n*(n+1)/2 formula).
Sum of A can be found by iterating through all i and adding up 2^i * (count of numbers having bit i as the smallest bit).

Also, you need to consider N=2^i independently since A=B=-1 in that case.

9 Likes
7

After doing some math ā€¦ I did not do ā€œmore mathā€.

1 Like
8

can someone please tell me whatā€™s wrong in my solution??

https://www.codechef.com/viewsolution/28453392

9

I would say my algo is really simple. You can observe that B is N after removing the least significant bit. If there is only one least significant bit, then B = -1 as B cannot be 0. So, you take sum of all integers from 1 to N, that is (N * (N + 1)) / 2. You subtract the (2 ^ number of trailing zeroes) for each number. This can be proved to be (floor(n / 1) * 1 + floor(n / 2) * 1 + floor(n / 4) * 2 + floor(n / 8) * 4 + floor(n / 16) * 8 +ā€¦). You have the sum now which is sum of all integers from 1 to N with (2 ^ number of trailing zeroes) subtracted from each of them. But we have missed one case, where B = 0. B is zero only when N is a power of 2. So we need to subtract (log2(N) + 1) from our sum as B = 0 is treated as B = -1. This will give the correct answer.

AC code - CodeChef: Practical coding for everyone

2 Likes
11

From a person whose bio tells me that he doesnā€™t like maths :stuck_out_tongue:

12

There are problems with much worse math :face_vomiting:

This problem is just a few simple formulas :confused:

2 Likes
13

How are we talking in terms of ā€˜sumā€™, when the operation mentioned is XOR? Please clarify, thanks!

14

Okay, what do we know about the XOR-operation? Some basic properties include:

  • \oplus is a binary relation, \oplus: S \times S \rightarrow S,where\ S = \{0, 1\}
  • A \oplus 0 = A, where\ A \in S summarized as:
    \textbf{zero is the identity element for } \oplus.
  • A \oplus B = 0 \Longleftrightarrow A = B, where\ A, B \in S, summarized as: \textbf{every element is its own inverse for } \oplus

Notice that the identity element for both \oplus and + is zero, which means when we add and xor two binary numbers (as xor deals only in zeroes and ones), we get the same output at positions where at least one of the two numbers is unset (has a 0). The only combination of that remains to be taken care of is when both operands (or positions in those numbers) are set. While xor nullifies them (since one is the inverse of the other for xor), the sum goes on to generate a carry (which do give the same output at the current position for the two operations but which changes their overall output).

Finally, in this problem, we never have a situation where a position is set in both A and B implying that the results of sum and xor of the two will be the same, and thus we can exploit this fact to ease our calculations. The proof as to why this is true is well-explained in the editorial :slightly_smiling_face:

15

Could you please explain how this formula gives us the required count of numbers having ind bit as set bit ! :slightly_smiling_face:
ct = ((r >> ind) / 2) + ( (r >> ind) % 2) - (((l-1) >> ind) / 2) - (((l-1) >> ind) % 2);