A not so easy problem on Set of Numbers

Revision en4, by rachitiitr, 2018-02-10 13:06:00

Hi

I frequently think of problems on my own, and try to solve them.
But this simple problem got me dazzled!

Problem Description:
You have a set A, size N, Ai upto 109.
You play N - 1 steps on it.
Each step, pick any 2 elements x, y and remove both of them. Add back abs(x - y) to A.
Print the max value possible at end.

I was thinking that DP might solve this, but I was wrong about the approach that was coming to my mind.

My Approach:
The ans can't be greater than max element, say M.
So find out the minimum possible value that you can have from the remaining N - 1 elements.
A simple DP can be used for this, but this approach is wrong :)

Can anyone solve this?

Happy Coding!

Tags rachitiitr, rachitjain

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English rachitiitr 2018-02-10 13:06:00 31 Tiny change: 'ong :) \n\nH' -> 'ong :) \n\nCan anyone solve this? \n\nH'
en3 English rachitiitr 2018-02-09 22:01:19 2 Tiny change: 'h:** \n\nThe ans ' -> 'h:** \nThe ans '
en2 English rachitiitr 2018-02-09 22:01:03 283
en1 English rachitiitr 2018-02-09 21:58:25 526 Initial revision (published)