You start with 0 and you have to Find the minimum number of operations to reach 'n'. In one operation you can add or subtract any 2^k to your current number. Where k can be any positive integer.

Constraints:

test cases <200,000;

1 <= | n | <= 1,000,000,000 . Example:

INPUT:

First line is no. of test cases, then a single integer 'n' on each line.

5

1

2

0

6

10

OUTPUT:

1

1

0

2

2

Can anybody help??

Auto comment: topic has been updated by basantCoder (previous revision, new revision, compare).Why not try to reach from n to 0 by subtracting nearest power of 2(floor)

Maybe Like this...Hope its not live Rn

its not always optimal!

Like for 28 your code will give 3. But you can reach 28 is 2 operations also.

As any

`n`

can be represented in binary form which is nothing but sum of powers of 2. So the answer will be number of`1`

s in binary notation of`n`

. Example: $$$10 = (1010)_2$$$ Here count of`1`

s = 2 = answerfor example take n=28, binary form = (11100)

_{2}According to your logic: answer = 3.

But correct answer is 2. First operation add 32, second operation substract 4.

Your binary representation of 28 is wrong.

Thanks for correcting

Sorry, I missed this case. I think we can always create consecutive

`1`

's by subtracting(by taking a carry) in binary form, provided there is a

`1`

in the left.That is we can always replace continuous

`1`

s with 2 operations, putting a`1`

in the left and subtracting it by`1`

. Example: We want`1110`

So either it is 2 operations or (no of

`1`

bits) = x operations. We have to take minimum of it and sum all of such operations on consecutive`1`

s in the binary representation of`n`

to get the answer.codinginveins Consider n=7 According to your logic it will give 3 , but the correct answer is 2 (Add 8 then subtract 1).

https://codeforces.com/blog/entry/95133?#comment-841488

I still dont know if I am missing something here.

actually we can get cosecutive 1's and 0's format in 2 operations. Like is the number is (11111110000000)

_{2}. But still there can be complicated cases with random 1's and 0's where I am stuck.$$$ 111000111000111000_2 $$$ can be divided and conquered as sum of answers of $$$ 111000_2 $$$, $$$ 111000000000_2 $$$ and $$$ 111000000000000000_2 $$$. Infact it will also be equivalent to

We just need to process the segments where we get

`1`

s.`ans(1) = 1`

`ans(11) = 2`

`ans(111) = 2`

`ans(1111) = 2`

and so onto reduce time complexity you can do memoization

Let, f(x) = Number of set bit's in binary representation of x. Answer will be min(f(x), f(-x)).

Generate a vector with all powers of 2 less than equal to 1,000,000,000. Then use while(n > 0) n = n — lower_bound(n); Where lower bound on the generated array will return the power just less than N. This way you'll get the most optimal solution.

Had a hard time reading the title