sraj1614's blog

By sraj1614, history, 3 years ago, In English

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|);

  • Vote: I like it
  • -14
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    By the way do you have any where to submit. I once solved this problem but not sure why getting downvote

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      because this is codeforces :C

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 4   Vote: I like it +11 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

XOR M and N. The answer is the number of one bits in this value.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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$$$.

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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)).