Hello Guys! Recently i came across a question but couldn’t solve it efficiently. Please help.
The question is your’e given three numbers. You should perform the following operation on two numbers at a time: Subtract 1 from any two numbers. You have to do this until any of the number doesn’t become negative. And find the maximal number of operations you could perform on numbers.
Here’s what i tried:
I tried sorting everytime, taking the highest two numbers and subtracting. But TLE.
Again i also tried find max and second max and then subtracting. But TLE.
Ps. This was given in CGI Hackerearth Challenge!
Please help!
Thank you!
Peace!
Suppose a >= b >= c
First of we will continue performing operations on a till it becomes 0. While doing this we will choose either b or c as the other number.
If a > b + c, then the maximum number of operations is b + c, as only a will be the non-negative number after b + c operations
Now if a <= b + c, in this case when a becomes 0, we will be left with two numbers whose sum is b + c - a. Now we can perform the starting operation in such a way that the remaining values of b and c will be equal or nearly equal. More formally if b + c is even we can perform the starting operatons in such a way that the remaining values of b and c are equal.
Otherwise one of b and c will have and extra +1. Overall we will be able to perform min(b, c) more operations and then either one of b or c(or both) will become 0 and we will be left with two 0’s and one 1 (or three 0’s).
So the max number of operations will be
min(a, b + c) + max(0, (b + c - a) / 2)