Difficulty:
========
Easy
Prerequisites:
=
Logical thinking, Basic Programming
Problem:
=
We have to find minimum time in which Adam can get all the chocolates in one box, given N infinitely sized boxes.
Quick Explanation:
=======================
Sort array of inputs in ascending order. Add two consecutive array elements & store result in second element till array is complete.
Detailed explanation:
=
Take inputs from user & store candies in each box in the form of array. Since we have to find minimum time required, sort this array in ascending form. After sorting add each element of array with it’s consecutive next element ( i.e a[i] + a[i+1] ). Store result of addition in a[i+1] (we have to combine chocolates into one box.) In order to find minimum time, it is necessary that after each addition operation array list should be updated so that it is in ascending order.
For example, consider inputs as: 1 2 3 4 5
After 1st iteration- array : 1 3 3 4 5 ans : 3
2nd iteration- array : 1 3 6 4 5 ans : 9
Now here there are two possibilities either add 6 + 4 or sort array in ascending order and add 4 + 5
Method 1-
3rd iteration- array : 1 3 6 10 5 ans: 19
4th iteration- array : 1 3 6 10 15 ans : 34
Method 2 - [sorting array before adding consecutive elements]
After sorting : 1 3 4 5 6
3rd iteration- array : 1 3 4 9 6 ans: 18
After sorting: 1 3 4 6 9
4th iteration- array : 1 3 4 9 15 ans: 33
Thus, method 2 leads to optimal result.