How to efficiently count the number of pairs having a xor b equal to m where 1<=a<=n , 1<=b<=n and n varies 2 to 2e5 and m also varies 1 to n
How to efficiently count the number of pairs having a xor b equal to m where 1<=a<=n , 1<=b<=n and n varies 2 to 2e5 and m also varies 1 to n
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | Dominater069 | 131 |
| 9 | Proof_by_QED | 130 |
| 9 | AmShZ | 130 |
Hint: If a and m are fixed, can you find a value of b, such that a ^ b = m?
yeah b = m^a and complexity will be o(n) right?? got it ... it this final like cant we go beyond that like logarithmic or like lesser than this
My bad, you still need to check if the corresponding b is <= n, so n — 1 is not correct, in general it is less than that. So I failed in my attempt to make it better than O(n)
Good job! How many possible values of a are there?
(Don't overthink the complexity — what you are shooting for is O(n) )
For linear time we can just iterate a from 1 to n and check if the corresponding b is in 1 to n or nah. I think OP is asking for a sublinear algorithm.
well, n varies from 2 to 2e5, so a linear algorithm is good enough.
For a sublinear algorithm, we would need to do some more work.
I think a fruitful approach for this might be recursion.
If we can solve this problem with n = n/2, and m = m/2, I think we could use that result to solve n = n and m = m.
digit dp helps solve this problem with ease with larger N I guess
If you look at all bits in m, then if bit is 0, than this bit is same in a and b and if 1 than different. This already gives a linear time algorithm (you can take first bit, and go in two same recursion but memorizing how you change bit in a and b. It hase exponential branche factor but logariphmic number of levels, so it is linear. In other words, it works in O(2^{log(n)})=O(n)).
Let f(x,y,m,i) be function that return number of pairs a and b such that 1<=a<=x and 1<=b<=y and a^b=m and proccess only bits from 1 to i. Looking at the biggest bit of m, we can go in recursion same as in the solution above (if there should be i-th bit 1 in a and 0 in b, then return f(x-(1<<i),y,m-(1<<i),i-1)+f(x,y-(1<<i),m-(1<<i),i-1) for example). If x or y is 1, we can easily get answer (1^x would be x+1 or x-1, so it is just some ifs). Let's check some edge cases. If x>(1<<(i+1))-1 then we can make any number from bits from 1 to i, so we can assign x=(1<<(i+1))-1. Same for y. If x and y are powers of 2 minus 1, we can solve it easily. Firstly, if x=y and x=(1<<n)-1, then answer is x, because for any x, m^x is at most y (we assume that m has only i bits, because otherwise there are 0 pairs). Assume that y>x and y and x are power of 2 minus 1. Then we can assign any a and b will be m^a and there will also be such solution. So number of solutions are also x. If x<(1<<i), then we cannot decrease it in the recursion. Same for y.
Having all this we can come up with some solution. I believe it should work in O(log(n)), but it is clearly less then O(n). Here is code what I mean
int f(int x,int y,int m,int i)
{
if(x<0||y<0||m<0||m>=(1<<(i+1))) { return 0; } if(x>=(1<<(i+1))) { x=(1<<(i+1))-1; } if(y>=(1<<(i+1))) { y=(1<<(i+1))-1; } if((x&(x+1))==0&&(y&(y+1))==0) { return min(x,y)+1; } int b=(m>>i)%2; if(b==1) { return f(x-(1<<i),y,m-(1<<i),i-1)+f(x,y-(1<<i),m-(1<<i),i-1); } else { return f(x-(1<<i),y-(1<<i),m,i-1)+f(x,y,m,i-1); }}
This code doesn't work now, but it should show the idea that I mean. Also, with this if's it should also go in two recursions, but one of them will get into some of first if's, so should proccess in constant time.