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.
2 3 4
(2 3 4-> 2 2 3-> 2 1 2-> 1 1 1-> 0 0 1)
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!
min((a+b+c)/2 ,a+b), I think.
My solution worked, but unfortunately I dint get enough time to complete the test.
This was asked in Google assesment test.
Code is just for rough purpose and I know there is no clean code approach or complexity is taken care.
sort the three numbers
suppose a >= b >= c
then the answer is min(a, b + c)
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)
where a >= b >= c