Minimum cost to merge numbers from 1 to N | C ++ program to find the Minimum cost to merge numbers from 1 to N . ; Function returns the minimum cost ; Min Heap representation ; Add all elements to heap ; First minimum ; Second minimum ; Multiply them ; Add to the cost ; Push the product into the heap again ; Return the optimal cost ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int GetMinCost ( int N ) { priority_queue < int , vector < int > , greater < int > > pq ; for ( int i = 1 ; i <= N ; i ++ ) { pq . push ( i ) ; } int cost = 0 ; while ( pq . size ( ) > 1 ) { int mini = pq . top ( ) ; pq . pop ( ) ; int secondmini = pq . top ( ) ; pq . pop ( ) ; int current = mini * secondmini ; cost += current ; pq . push ( current ) ; } return cost ; } int main ( ) { int N = 5 ; cout << GetMinCost ( N ) ; }