• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Connect n ropes with minimum cost

August 19, 2014 by Dhaval Dave

Connect n ropes: There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.

Diff ways to connect

1) As it is… count = 4+3 = 7 , count = 7(previous)+ 7+2 = 16 , count = 16(previous)+9+6 =31.
2) Longest first
Array = 6,4,3,2
count = 6+4 =10 , count = 10+10+3=23 , count = 23+23+2 =48.

From above discussion we can understand that lengths of the ropes which are picked first are included more than once in total cost, hence we can say that choosing smallest ropes first will give optimal solution.

code

#include <iostream>
#include <stdio.h>
#include <array>
#include <algorithm>
using namespace std;
#define MAX 100
#define gc getchar_unlocked

inline int scan(){register int n=0,c=gc();while(c<'0'||c>'9')c=gc();while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=gc();return n;}
int getCount(int n[],int len,int c)
{  
    int i=0;
    if(n[i+1]!=9999){ 
    n[i+1]+=n[i];
    n[i]=9999;
    c+=n[i+1];
    sort(n,n+len);
    }
    if(n[i+1]==9999)return c;
    if(len>0) getCount(n,len-1,c);
}

int main()
{
   int len=scan();
   int j = len;
   int n[MAX];
   int sum=0;
   int i = 0;
   while(j--){
       n[i++]=scan();
   }
   j=len;
   
    sort(n,n+len);
    sum=getCount(n,len,sum);
    cout<<"Sum is="<<sum;
    return 0;
}
//STDIN : 4 2 4 3 6

Complexity : O(n^2 logn)
O(n) to get all ropes * O(nlogn) sorting array each time.
See running code : http://ideone.com/89GG37

Solution 2 :  Use Min Heap instead sorting array every time
Logic:
1) Store array’s element in Min heap.
do
2) Get first minimum and second minimum
3) Add them and store result in min heap and update “SUM”.
while(heap’s length > 1)

=> Try to implement yourself :)

Similar Articles

Filed Under: Flipkart Interview Questions, Interview Questions, problem Tagged With: Array

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Doubly linked list

FizzBuzz Solution C C++

Given a float number convert it into the string WITHOUT using any inbuilt Function

Generic Object Oriented Stack with Template

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Find the smallest window in a string containing all characters of another string

CodeChef Code SGARDEN

Right view of Binary tree

Find Percentage of Words matching in Two Strings

Walmart Labs Interview Experience

Find two non repeating elements in an array of repeating elements

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Binary Tree Isomorphic to each other

Printing intermediate Integers between one element & next element of array

Search element in a matrix with all rows and columns in sorted order

SAP Off Campus Hiring_ March 2015 Sample Questions

Facebook Interview Question : Interleave List

Edit Distance ( Dynamic Programming )

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Password Predictor

Trie Dictionary

Word Break Problem

Max Sum in circularly situated Values

Code Chef PRGIFT Solution

Maximum of all subarrays of size k

Wrong Directions given find minimum moves so that he can reach to the destination

C++ OOPs Part1

Stock Buy Sell to Maximize Profit

Copyright © 2025 · Genesis Framework · WordPress · Log in