• 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

Sequence Finder Dynamic Programming

Linked List V/S Binary Search Tree

Client Server C program

Interfaces in C++ (Abstract Classes in C++)

Printing each word reverse in string

Find min element in Sorted Rotated Array (With Duplicates)

SAP Off Campus Hiring_ March 2015 Sample Questions

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

Generate largest number arranging a no. of given non negative integer numbers

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Trie Dictionary

Find if a binary tree is height balanced ?

Minimum insertions to form a palindrome

Closed Parentheses checker

How Radix sort works

Coin Collection Dynamic Programming

ADOBE Aptitude C Language Test

Find the kth number with prime factors 3, 5 and 7

Practo Hiring Experience

C Program for TAIL command of UNIX

CodeChef’ RRCOPY

Difference between a LinkedList and a Binary Search Tree BST

Calculate price of parking from parking start end time prices

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

C++ OOPs Part1

Length of the longest substring without repeating characters

Reverse a Linked List in groups of given size

Flipkart Set 1 On Campus with Answers

Reversal of LinkedList

Best Java Book | Top Java Programming Book for Beginners

Copyright © 2025 · Genesis Framework · WordPress · Log in