Problem LinkAuthor: Jitender Sheora Tester: Mark Mikhno Editorialist: Bhuvnesh Jain DifficultySIMPLE PrerequisitesPrecomputation, Binarysearch ProblemYou are given a number $N$ and you can apply 2 type of operations:
Find the minimum number of operations to be carried such that the resulting number can be represented as $2^x + 2^y$, where $x$ and $y$ are nonnegative and $x != y$. ExplanationThe first thing to note is the optimal answer requires us to apply the only operation of either type. Since the operations negate the effect of each other, we should either only add or subtract from our initial number $N$. Suppose, if we have a sorted list of all possible final numbers which can be represented in the form, $2^x + 2^y$, then we can simply find the number nearest to $N$. For the smaller number, we can simply apply subtraction operation and for the greater number, we can simply apply the addition operation. For finding the nearest number greater than or smaller than a given number, we can simply binary search. If you are not familiar with this, you can read topcoder tutorial. There are also inbuiltfunctions like "lower_bound" and "upper_bound" in C++ which do your job. (But remember your list should be sorted.) We can now precomputate all possible numbers which can be represented in the form $2^x + 2^y$. Below is a pseudocode for it:
Note that the maximum possible exponent of $2$ in answer can be $ceil(\log{{10}^9}) = 30$. This is because, for the minimum operation, we need to find the nearest possible number closest to $N$. The size of $vals$ will be $(31 * 30) / 2) = 465$. Since the size is not large, even iterating through all numbers, instead of applying binary search will pass for the full solution. Once, you are clear with the above idea, you can see the author or editorialist implementation below for help. Feel free to share your approach, if it was somewhat different. Time Complexity$O({\log}^2{N})$ for precomputation. $O({\log{vals}})$ per test case. Space Complexity$O({\log}^2{N})$ SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here. asked 13 Aug '18, 15:00

My approach was to search directly. First 'decode' the number, counting the number of binary ones, and finding the zerobased position of the first and second binary digits. For a number with more than 2 binary digits, there are two possibilities. For a number 'n' (a) Subtract to remove digits less significant than the first two
(b) Add to leave only 2 binary digits
Choose whichever is the less. You can see the solution at https://www.codechef.com/viewsolution/19485795 answered 14 Aug '18, 05:38

Video solution with explanation (C++, Java, Python): https://youtu.be/yMxoRT381yQ answered 13 Aug '18, 15:22

First, for numbers $4$ or less, find the difference to $3$, the smallest qualifying value. Then starting with $8$, I doubled up to find the smallest power of $2$ not less than $n$, then stepped back down by smaller powers of $2$ until I had $n$ bracketed. so for example for $n=39$ the trail would go $8\to 16\to 32\to 64\to 48\to 40\to 36,$ with the result following from $\min(4039, 3936) =1.$ At the turn point the top of the bracket is held (if needed) as $65=64+1.$ answered 14 Aug '18, 06:28

whats wrong with my code https://www.codechef.com/viewsolution/19615761 Fist I checked if the number is 1 or equal to square's then we can get the number of steps directly. if don't then I subtract the given number with square number in list bigger than it, keep the difference in d. then checking the closet square to d is the number of steps required If u can please run it and find any test case that it fails, plz comment it answered 14 Aug '18, 08:58

the above solution is failing in last test case.Can anyone suggest where I am doing wrong?? answered 14 Aug '18, 09:02

If the binary representation of $N$ has only one set bit then the answer is $1$, unless $N = 1$, in which case the answer is $2$. Let 2 or more bits are set in the binary representation of $N$. Find the two numbers $l$ and $h$ such that $l$ is the largest number represented as $2^x+2^y$ that is not greater than $N$, and $h$ is the smallest number represented as $2^x+2^y$ that is greater than $N$. Let $b_1$ be the number corresponding to the highest set bit in the binary representation of $N$, and $b_2$  to the second highest. Then $l=b_1 + b_2$ and $h=b_1+2b_2$ if $b_1>2b_2$, otherwise $h=b_1+2b_2+1$. The answer is the smallest of the distances from $N$ to $l$ and $h$. answered 14 Aug '18, 11:18

https://www.codechef.com/viewsolution/19638812 Different approach... answered 14 Aug '18, 14:14

My solution is not working for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013 answered 14 Aug '18, 15:44

I found out the highest value of 2^x which is less than or equal to the given number and iterated y from 0 to x1 adding both the values of 2^x and 2^y.If the sum is less than or equal to the given number I am updating the value of temp and if the sum is greater than or equals to the given number I am assigning the value to temp1 and breaking the loop.If sum never equals or exceeds the number temp1 is assigned with (2^(x+1))+1 which has 2 set bits(in the form of (2^x+2^y)). The minimum of the absolute difference between temp and temp1 is the answer.I can't figure out what could probably go wrong in this.So if you could please test it and correct my code I would be thankful.This is the link to my solution link text. Kindly check it. answered 14 Aug '18, 18:05

My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650
link
This answer is marked "community wiki".
answered 14 Aug '18, 22:25

My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ciel and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650
link
This answer is marked "community wiki".
answered 14 Aug '18, 22:25

My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650
link
This answer is marked "community wiki".
answered 14 Aug '18, 22:25

My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650
link
This answer is marked "community wiki".
answered 14 Aug '18, 22:25

My approach was using log function , then by approximating the nearest value of the given number by taking log and then applying ceil and floor of the given value there must be either one power of 2 solving the given problem , thus by clever approximations to power of 2 i got AC :) check it out : https://www.codechef.com/viewsolution/19619650
link
This answer is marked "community wiki".
answered 14 Aug '18, 22:25

include <iostream>include <math.h>include <vector>include <bits stdc++.h="">include <algorithm>using namespace std; int main() { vector <long long="" int=""> v1; int i,j,n1,t,flag=0; long long int n; for(i=0;i<=30;i++) { for(j=i+1;j<=30;j++) { n1=pow(2,i)+pow(2,j); v1.push_back(n1); } } sort(v1.begin(),v1.end()); vector <long long="" int=""> ::iterator lower,upper; cin>>t; while(t) { cin>>n; for(auto itr=v1.begin();itr!=v1.end();itr++) { if(itr==n) { cout<<'0'<<endl; flag=1; break; } else if(n==1) { cout<<'2'<<endl; flag=1; break; } else if(n==2) { cout<<'1'<<endl; flag=1; break; } } if(flag==0) { for(auto itr=v1.begin();itr!=v1.end();itr++) { lower=lower_bound(v1.begin(),v1.end(),n)1; upper=upper_bound(v1.begin(),v1.end(),n); if(nlower<=uppern) { cout<<nlower<<endl; break; } else { cout<<*uppern<<endl; break; } } } } return 0; } plz tell me what is wrong with my code?
link
This answer is marked "community wiki".
answered 18 Aug '18, 09:00

Please tell why my solution isn't working for all the inputs..... include<bits stdc++.h="">using namespace std; int main() { int t; cin>>t; while(t) { long int n; cin>>n;
} answered 18 Aug '18, 13:11

I'm getting TLE and WA. Please tell me some of the edge cases where I might get a wrong output and also how can I optimize it more. Thank you. answered 17 Oct '18, 16:31

I'm getting TLE and WA. Please tell me some of the edge cases where I might get a wrong output and also how can I optimize it more. Thank you.
link
This answer is marked "community wiki".
answered 17 Oct '18, 16:31

I'm getting TLE and WA. Please tell me some of the edge cases where I might get a wrong output and also how can I optimize it more. Thank you.
link
This answer is marked "community wiki".
answered 17 Oct '18, 16:31
