Optimal game strategy

#1

pls, point out mistakes in this code.
it is showing run error for two test cases and wrong answer for one.

#2

Hi Keshav,
Consider the following input:
4
8 15 3 7
Expected output: 22
Your output: 15

you’re using greedy approach in this. You’re choosing the locally optimal solution at every step i.e. you’re choosing the maximum valued coin at every step. This approach will not provide us the globally optimal solution always like in the case I mentioned earlier. You need to think of some other logic that will always give the optimal solution.

here is the algo:
(1) Count the sum of all coins that are odd-numbered. (Call this X)
(2) Count the sum of all coins that are even-numbered. (Call this Y)
(3) If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
(4) If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
(5) If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.