### sraj1614's blog

By sraj1614, history, 6 weeks ago,

Given an integer N and M(initially M=0). You can do the following operations - Create an integer K and add 2^k to M. Create an integer K and subtract 2^k from M. Find the minimum number of operations to make M equal to N

Input Format- The first line of input contains a single integer T-number of test case The first line of each test case contains a single integer M.

Constraint- N<=2*10^5 |M|<=10^9

Expected Complexity per test case -log(|M|);

• -14

 » 6 weeks ago, # |   -17 Let define $dp[i][x]$ = minimum operations to make $M$ equal $N$ in all bits $i, i + 1, \dots \left \lceil log_2(n) \right \rceil$ and $[x] = true$ when the bits $0, 1, \dots i$ is currently flipped
•  » » 4 weeks ago, # ^ |   +19 By the way do you have any where to submit. I once solved this problem but not sure why getting downvote
•  » » » 4 weeks ago, # ^ |   +1 because this is codeforces :C
•  » » » » 4 weeks ago, # ^ | ← Rev. 4 →   +11 Maybe I get more downvotes because I have low-rank and didnt give a detail answer. No offensive but well this make sense when people with more rating tend to think more deep, careful and correct when giving an answer.Though there is a fact that some lower rankers can still provide a quality answer like once I have seen a newbie get 35 downvotes even when his solution is impressively correct.
 » 4 weeks ago, # |   0 XOR M and N. The answer is the number of one bits in this value.
•  » » 4 weeks ago, # ^ |   +16 This isn't correct. If $N = 7$ and $M = 0$, then with your idea, the answer is $3$. However, it is possible do this in $2$ operations, by first adding $2^3$, then subtracting $2^0$.
 » 4 weeks ago, # |   +13 The statement isn't 100% clear, so my comment assumes $M=0$, $N \leq 10^9$.A search on the OEIS yields the sequence A007302. There's a few formulas listed, including the one-liner __builtin_popcount(n ^ (3 * n)).