• 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

Skiing on Mountains Matrix

Longest Increasing Subsequence

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

Flipkart SDET Interview Experience

Find min element in Sorted Rotated Array (Without Duplicates)

Implement a generic binary search algorithm for Integer Double String etc

Printing each word reverse in string

Facebook Interview Question : Interleave List

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Urban Ladder Written Test.

Reversal of LinkedList

LeetCode : Word Search

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

Handle duplicates in Binary Search Tree

Maximum of all subarrays of size k

C Program for TAIL command of UNIX

Check Binary Tree is Binary Search Tree or not

Printing intermediate Integers between one element & next element of array

Find and print longest consecutive number sequence in a given sequence in O(n)

C++ OOPs Part1

Add Sub Multiply very large number stored as string

Closed Parentheses checker

Trapping Rain Water

Hackerearth : Counting Subarrays

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

Count Possible Decodings of a given Digit Sequence

Doubly linked list

Given Set of words or A String find whether chain is possible from these words or not

Find next greater number with same set of digits

Mirror of Tree

Copyright © 2025 · Genesis Framework · WordPress · Log in