Amazon Online Assessment (OA) - Connect Ropes
Given n
ropes of different lengths, you need to connect these ropes into one rope.
You can connect only 2
ropes at a time. The cost required to connect 2
ropes is equal to the sum of their lengths
.
The length of this connected rope is also equal to the sum of their lengths
.
This process is repeated until n
ropes are connected into a single rope.
Find the minimum possible cost required to connect all ropes.
Input
The input consists of an argument:
ropes
: an int array representing the rope length
Output
Return the minimum possible cost required to connect all ropes.
Examples
Example 1:
Input: [8, 4, 6, 12]
Output: 58
Explanation:
The optimal way to connect ropes is as follows
- Connect the ropes of length
4
and6
(cost is10
). Ropes after connecting:[8, 10, 12]
- Connect the ropes of length
8
and10
(cost is18
). Ropes after connecting:[18, 12]
- Connect the ropes of length
18
and12
(cost is30
).
Total cost to connect the ropes is 10 + 18 + 30 = 58
Example 2:
Input: [20, 4, 8, 2]
Output: 54
Example 3:
Input: [1, 2, 5, 10, 35, 89]
Output: 224
Example 4:
Input: [2, 2, 3, 3]
Output: 20
Try it yourself
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.