### basantCoder's blog

By basantCoder, history, 5 weeks ago, 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?? Comments (16)
 » Auto comment: topic has been updated by basantCoder (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 4 →   Why not try to reach from n to 0 by subtracting nearest power of 2(floor) long long n,ans=0; cin>>n; while(n>0){ n = n - pow(2,(int)__lg(n)); ans++; } cout<
•  » » 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 1s in binary notation of n. Example: $10 = (1010)_2$ Here count of 1s = 2 = answer
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   for 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
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   Sorry, I missed this case. I think we can always create consecutive 1's by subtracting $0 - 1 = 10$(by taking a carry) in binary form, provided there is a 1 in the left. That is we can always replace continuous 1s with 2 operations, putting a 1 in the left and subtracting it by 1. Example: We want 1110 $10000 - 10 = 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 1s 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-841488I 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.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 5 →   $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 $ans(111000_2) + ans(111000_2) + ans(111000_2) = 3 * ans(111_2)$We just need to process the segments where we get 1s. ans(1) = 1 ans(11) = 2 ans(111) = 2 ans(1111) = 2 and so on
 » 5 weeks ago, # | ← Rev. 4 →   int recur(n){ if(n == 0) return 0; else if((n & (n - 1)) == 0) return 1; int temp 1e9; for(int i = 0; i <= 14; i++){ int val = abs(n - (1 << i)); temp = min(temp, 1 + recur(val)); } return temp; } void solve() { ll n; cin >> n; n = abs(n); cout << recur(n); } to 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.