Help in pairwise AND

[vkkr125]

hello guys can you help with this : CodeChef: Practical coding for everyone

[claro_henrique]

try to solve the problem for n= 1, 2, 4, 8, 16, …
if you have the answer using only X bits, can you find the solution for X+1 bits?

[cubefreak777]

Help in pairwise AND problem

Most probably I overkilled the solution so feel free to ignore it, I’d appreciate if someone can share a neater solution. So for any given N we have to calculate the following S, S=1\&2+2\&3+3\&4+ \cdots + (N-1)\&N S= \underbrace{2\&3+4\&5+6\&7+ \dots }_\text{Even \& Odd} +\underbrace{1\&2+3\&4+5\&6 + \dots }_\text{Odd\& Even} Now we will use the standard trick of bit manipulation. let c[i] be the number of terms where bit i is set. So final answer would just be S=\displaystyle\sum_{i=…

If this helps.

[claro_henrique]

if you look the binary representation for N=29, you can see that a bit 1 with an adjacent bit 1 appear periodically. You can use that to count the active bits in the i-th collumn and multiply by 2^i.

my solution: https://www.codechef.com/viewsolution/44318769