• 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

Print all nodes that are at distance k from a leaf node

Skiing on Mountains Matrix

Implement LRU Cache

LeetCode : Word Search

Leetcode: Merge Intervals

Difference between a LinkedList and a Binary Search Tree BST

Edit Distance ( Dynamic Programming )

Longest Increasing Subsequence

Generic Object Oriented Stack with Template

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Find two non repeating elements in an array of repeating elements

Templates in C++

Max Sum in circularly situated Values

Find loop in Singly linked list

Get K Max and Delete K Max in stream of incoming integers

Coin Collection Dynamic Programming

Linked List V/S Binary Search Tree

ADOBE Aptitude C Language Test

SAP Interview Questions

Print vertical sum of all the axis in the given binary tree

Advanced SQL Injection

Closed Parentheses checker

C Program for TAIL command of UNIX

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

VMWare SDEII Interview

Practo Hiring Experience

C++ OOPs Part2

C++ OOPs Part1

Find Percentage of Words matching in Two Strings

Best Java Book | Top Java Programming Book for Beginners

Copyright © 2025 · Genesis Framework · WordPress · Log in