FIND THE MAXIMUM NUMBER OF OPERATIONS - HELP

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.

Ex:
2 3 4 
o/p:
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!
Please help!
Thank you!
Peace! :slight_smile:

min((a+b+c)/2 ,a+b), I think.

2 Likes


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