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|);
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
By the way do you have any where to submit. I once solved this problem but not sure why getting downvote
because this is codeforces :C
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.
XOR M and N. The answer is the number of one bits in this value.
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$$$.
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)).