Data Modelling & AI Data Structure & Algorithm

Find the minimum cost to cross the River

21 June 2025

0

Given an integer N which is the number of villagers who need to cross a river but there is only one boat on which a maximum of 2 person can travel. Each person i has to pay some specific price P_i to travel alone in the boat. If two person i, j travel in the boat then they have to pay max(P_i, P_j). The task is to find the minimum amount all the villagers have to pay to cross the river.
Examples:

Input: Price[] = {30, 40, 60, 70}
Output: 220
P₁ and P₂ go together (which costs 40)
and P₁ comes back (total cost 70 now).
Now P₃ and P₄ go (total cost 140) and
P₂ comes back (total cost 180) and
finally P₁ and P₂ go together (total cost 220).
Input: Price[] = {892, 124}
Output: 892

Approach: There are two ways for the two most costly person to cross the river:

Both of them cross the river with the cheapest person turn by turn. So, the total cost will be the cost of the two costly persons + 2 * (cost of the cheapest person) (due to coming back).
The two cheapest person cross the river and the cheapest person comes back. Now, the 2 most costly person cross the river and 2nd cheapest person comes back. So, the total cost will be the cost of the cheapest and costliest person plus 2 * cost of the second cheapest person.
Total cost will be the minimum of the above two ways.

Let’s consider the example we used above to understand the approach:
P₁ = 30, P₂ = 40, P₃ = 60, P₄ = 70
According to first method, P₄ goes with P₁ and P₁ comes back (cost is P₄+P₁).
Now, P₃ goes with P₁ and P₁ comes back (cost for this ride will be P₄+P₁).
So, total cost for sending two most costly person according to method 1 is P₄+2*P₁+P₃ = 190
According to second method, P₂ goes with P₁ and P₁ comes back (cost is P₂+P₁).
Now, P₃ goes with P₄ and P₂ comes back (cost for this ride will be P₄+P₂).
So, total cost for sending two most costly person according to method 2 is P₄+2*P₂+P₁ = 180
Hence, cost for sending P₃ and P₄ will be minimum of 2 methods, i.e., 180.
Now, we are left with P₁ and P₂ whom we have to send together and cost will
be P₂ = 40.
So, total cost for travelling is 180 + 40 = 220.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
// Function to return the minimum cost
int minimumCost(ll price[], int n)
{
 
    // Sort the price array
    sort(price, price + n);
    ll totalCost = 0;
 
    // Calculate minimum price
    // of n-2 most costly person
    for (int i = n - 1; i > 1; i -= 2) {
        if (i == 2) {
            totalCost += price[2] + price[0];
        }
        else {
 
            // Both the ways as discussed above
            ll price_first = price[i] + price[0] + 2 * price[1];
            ll price_second = price[i] + price[i - 1] + 2 * price[0];
            totalCost += min(price_first, price_second);
        }
    }
 
    // Calculate the minimum price
    // of the two cheapest person
    if (n == 1) {
        totalCost += price[0];
    }
    else {
        totalCost += price[1];
    }
 
    return totalCost;
}
 
// Driver code
int main()
{
    ll price[] = { 30, 40, 60, 70 };
    int n = sizeof(price) / sizeof(price[0]);
 
    cout << minimumCost(price, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
    // Function to return the minimum cost
    static long minimumCost(long price[], int n)
    {
     
        // Sort the price array
        Arrays.sort(price);
         
        long totalCost = 0;
     
        // Calculate minimum price
        // of n-2 most costly person
        for (int i = n - 1; i > 1; i -= 2)
        {
            if (i == 2)
            {
                totalCost += price[2] + price[0];
            }
            else
            {
     
                // Both the ways as discussed above
                long price_first = price[i] + price[0] + 2 * price[1];
                long price_second = price[i] + price[i - 1] + 2 * price[0];
                totalCost += Math.min(price_first, price_second);
            }
        }
     
        // Calculate the minimum price
        // of the two cheapest person
        if (n == 1)
        {
            totalCost += price[0];
        }
        else
        {
            totalCost += price[1];
        }
     
        return totalCost;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        long price[] = { 30, 40, 60, 70 };
        int n = price.length;
     
        System.out.println(minimumCost(price, n));
    }
}
 
// This code is contributed by AnkitRai01

Python

# Python3 implementation of the approach
 
# Function to return the minimum cost
def minimumCost(price, n):
 
    # Sort the price array
    price = sorted(price)
    totalCost = 0
 
    # Calculate minimum price
    # of n-2 most costly person
    for i in range(n - 1, 1, -2):
        if (i == 2):
            totalCost += price[2] + price[0]
 
        else:
 
            # Both the ways as discussed above
            price_first = price[i] + price[0] + 2 * price[1]
            price_second = price[i] + price[i - 1] + 2 * price[0]
            totalCost += min(price_first, price_second)
 
    # Calculate the minimum price
    # of the two cheapest person
    if (n == 1):
        totalCost += price[0]
 
    else:
        totalCost += price[1]
 
    return totalCost
 
# Driver code
 
price = [30, 40, 60, 70]
n = len(price)
 
print(minimumCost(price, n))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the minimum cost
    static long minimumCost(long []price, int n)
    {
     
        // Sort the price array
        Array.Sort(price);
         
        long totalCost = 0;
     
        // Calculate minimum price
        // of n-2 most costly person
        for (int i = n - 1; i > 1; i -= 2)
        {
            if (i == 2)
            {
                totalCost += price[2] + price[0];
            }
            else
            {
     
                // Both the ways as discussed above
                long price_first = price[i] + price[0] + 2 * price[1];
                long price_second = price[i] + price[i - 1] + 2 * price[0];
                totalCost += Math.Min(price_first, price_second);
            }
        }
     
        // Calculate the minimum price
        // of the two cheapest person
        if (n == 1)
        {
            totalCost += price[0];
        }
        else
        {
            totalCost += price[1];
        }
     
        return totalCost;
    }
     
    // Driver code
    public static void Main ()
    {
        long []price = { 30, 40, 60, 70 };
        int n = price.Length;
     
        Console.WriteLine(minimumCost(price, n));
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
    // Javascript implementation of the approach
     
    // Function to return the minimum cost
    function minimumCost(price, n)
    {
       
        // Sort the price array
        price.sort();
           
        let totalCost = 0;
       
        // Calculate minimum price
        // of n-2 most costly person
        for (let i = n - 1; i > 1; i -= 2)
        {
            if (i == 2)
            {
                totalCost += price[2] + price[0];
            }
            else
            {
       
                // Both the ways as discussed above
                let price_first = price[i] + price[0] + 2 * price[1];
                let price_second = price[i] + price[i - 1] + 2 * price[0];
                totalCost += Math.min(price_first, price_second);
            }
        }
       
        // Calculate the minimum price
        // of the two cheapest person
        if (n == 1)
        {
            totalCost += price[0];
        }
        else
        {
            totalCost += price[1];
        }
       
        return totalCost;
    }
     
    let price = [ 30, 40, 60, 70 ];
    let n = price.length;
 
    document.write(minimumCost(price, n));
             
</script>

Output:

Time Complexity: O(n * log n)

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Find the minimum cost to cross the River

C++

Java

Python

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US