Problem Link : Obtain Two Zeroes
The editorial have very nice solution But what if we have to print X for every operation and also minimum number of operation is intended. Then According to me Binary Search based solution worked here.
And One more thing as this Problem is tagged as Binary Search problem so it made me more curious.
Please help me to write Binary search based solution.
I don't see why you would need binary search to get optimal solution. My aproach is:
First asuming that a<b (a==b is a simple case, apply
op1(a/3)
andop2(2*a/3)
), you know that applying operation 1 with value b-a will get you toa-(b-a), b-2*(b-a) = 2a-b, 2a-b
. This is again solveable in 2 operations so for a pair of distinct numbers, you can get 3 operations.But notice that the operations can be combined. First, assume that you apply
op1(x)
and thenop1(y)
. This changesa, b
toa-x-y, b-2x-2y = a-(x+y), b-2*(x+y)
. But that is the same result we would have gotten by doingop1(x+y)
. So in the worst case, you should only need 2 operations: one of the first type, one of the second. To solve this you can just get the 3 values and combine them into 2.One final notice is that in the case when 2*a==b or 2*b==a you have a solution in one operation.