Given N gold wires, each wire has a length associated with it. At a time, only two

Given N gold wires, each wire has a length associated with it. At a time, only two adjacent small wires are assembled at the end of a large wire and the cost of forming is the sum of their length. Find the minimum cost when all wires are assembled to form a single wire.

For Example:

Suppose, Arr[]={7,6,8,6,1,1,}

{7,6,8,6,1,1}-{7,6,8,6,2} , cost =2

{7,6,8,6,2}- {7,6,8,8}, cost = 8

{7,6,8,8} – {13,8,8}, cost=13

{13,8,8} -{13,16}, cost=16

{13, 16} – {29}, cost =29

2+8+13+16+29=68

Hence , the minimum cost to assemble all gold wires is 68.

Constraints

  • 1<=N<=30
  • 1<= Arr[i]<=100

Example 1:

Input 

6  -> Value of N, represent size of Arr

7  -> Value of Arr[0], represent length of 1st wire

6 -> Value of Arr[1], represent length of 2nd wire

8 -> Value of Arr[2] , represent length of 3rd wire

6 -> Value of Arr[3], represent length of 4th wire

1 -> Value of Arr[4], represent length of 5th wire

1 -> Value of Arr[5], represent length of 6th wire

Output :

68 

Example 2:

Input 

4   -> Value of N, represents size of Arr

12  -> Value of Arr[0], represents length of 1st wire 

2   -> Value of Arr[1], represent length of 2nd wire

2   -> Value of Arr[2], represent length of 3rd wire

5  -> Value of Arr[3], represent length of 4th wire

Output :

34

Solution In Java

import java.util.*;
class Solution
{
public static int solve (int arr[], int n)
{
PriorityQueue <Integer> queue = new PriorityQueue<Integer>();

for (int i = 0; i < n; i++)
queue.add (arr[i]);

int sum = 0, temp1, temp2;

while (queue.size () >= 2)
{
temp1 = queue.poll ();
temp2 = queue.poll ();
sum += temp1 + temp2;
queue.add (temp1 + temp2);
}
return sum;
}

public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int arr[] = new int[n];

for (int i = 0; i < n; i++)
arr[i] = sc.nextInt ();

System.out.println (solve (arr, n));
}
}

Additional Reading

Also Read:

Acids, Bases and Salts-MCQ

Amazon Quiz MCQ Type Questions

Accenture MCQ Model Question Paper For 2022

Accenture MCQ Quantitative Aptitude Questions And Answers

Accenture MCQ Aptitude Questions And Answers

Top 30 MCQs for Your Data Science Interviews

Data Science MCQs For Written Exam

Time and Work Aptitude MCQ Questions & Answers for Infosys,TCS,Wipro

Core Java Multiple Choice Questions With Answers 2022

Infosys Mcq types Aptitude Questions for 2022

Latest Wipro MCQ Placement Paper

TCS Ninja Programming MCQ Questions with Answers

Amazon Aptitude Questions and Answers 2022

Data Science MCQ Questions 2022

Leave a Comment