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.

Question

Accepted Answer

Given N gold wires with lengths, find minimum cost to assemble all wires into a single wire.

Only two adjacent small wires can be assembled at a time
Cost of forming is the sum of their length
Use dynamic programming to find minimum cost
Example: N=4, lengths=[2,3,4,5], minimum cost=29

Accepted Answer

import java.util.*;
 class Solution
 {
  public static int solve (int arr[], int n)
  {
  PriorityQueue queue = new PriorityQueue();
  
  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));
  }
 }

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.

Top TCS ASE interview questions & answers

Popular interview questions of ASE

Top HR questions asked in TCS ASE