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 of1
s in binary notation ofn
. Example: $$$10 = (1010)_2$$$ Here count of1
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 a1
in the left and subtracting it by1
. Example: We want1110
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 consecutive1
s in the binary representation ofn
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.net/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)).
Had a hard time reading the title