{"id":1430,"date":"2020-06-11T03:54:41","date_gmt":"2020-06-11T03:54:41","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1430"},"modified":"2022-03-23T11:52:22","modified_gmt":"2022-03-23T11:52:22","slug":"become-king","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/become-king\/","title":{"rendered":"BECOME KING"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Greedy algorithm, Priority Queues<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Himanshu now wants to become the king. He has
\nN persons to defeat before he can become the King. He can choose any two persons and can fight with them, the strength needed for this is equal to the sum of both the persons. But whenever two persons are defeated they get killed and a new person borns with the combined strength of two person defeated. The fight continues until there is only one person left.Help Himanshu find the minimum strength he should waste to become king.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
1\n3\n2 3 4\n\n14\n\nHimanshu defeats 2 ,3 \nso the list of opponents becomes 5 ,4\nthen Himanshu defeats them.\nSo the strength required is (2+3)+(5+4)=14.\n<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
Since the new person born has the combined strength of two defeated persons, To minimize the strength of the new person and hence the total strength of king ,We must choose the two persons with the least strength at each iteration.<\/p>\n
For example, in the given test case, if Himanshu chooses the person with strength 2 and the person with strength 4 first ,the list becomes – 6,3 .<\/p>\n
Then after defeating them , the overall strength required becomes: 6+9=15 ,which is greater than what we got by selecting the least everytime.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
In order to minimize the sum, the people who get chosen at every step must be the ones with minimum strength from the list. In order to do that efficiently, a priority queue can be used.<\/p>\n
At each iteration, select the ones with minimum and second minimum strength .<\/p>\n
Add the two and push back the sum to the list.<\/p>\n
Also,keep updating the total sum!<\/p>\n<\/blockquote>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t