Minimum total cost incurred to reach the last station

0 0 5 minutes read

Given an array where each element denotes the number of chocolates corresponding to each station and to move from station i to station i+1, we get A[i] – A[i+1] chocolates for free, if this number is negative, we lose that many chocolates also.
You can only move from station i to station i+1, if we have non-negative number of chocolates.
Given the cost of one chocolate p, the task to find the minimum cost incurred in reaching last station from the first station (station 1).
Note: Initially we have 0 chocolates.
Examples:

Input : arr[] = {1, 2, 3}   p = 10
Output : 30
Initial choc_buy = 1 (arr[0])
To reach index 0 to 1, arr[0] - arr[1] = -1,
so choc_buy +=1.
Similarly To reach index 2 to 1, 
arr[1] - arr[2] = -1, so choc_buy +=1.
Total choc_buy = 3.
Total cost = choc_by * p = 3*10 = 30.

Input : arr[] = {10, 6, 11, 4, 7, 1}    p = 5
Output : 55
Initial choc_buy = 10 (arr[0])
To reach index 0 to 1, arr[0] - arr[1] = 4, 
so curr_choc =4.
Similarly To reach index 2 to 1, 
arr[1] - arr[2] = -5, so curr_choc=4+-5 = -1.
choc_buy += abs(-1).
So, similarly till last station, Total choc_buy = 11.
Total cost = choc_by * p = 11*5 = 55.

Approach :
1. Initialize choc_buy with the first element of array and curr_choc =0.
2. Add arr[i]-arr[i+1] to curr_choc for every i.
a) Check if curr_choc becomes negative.
choc_buy += abs(arr[i]- arr[i+1])
curr_choc = 0
3. Return choc_buy * p.

C++

// C++ program to calculate
// minimum cost for candies
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum cost
// to be incurred
int findMinCost(int arr[], int n, int choc_cost) {
 
  // To reach first station, initial
  // chocolates required
  int choc_buy = arr[0];
  int curr_choc = 0;
 
  // Start traversing
  for (int i = 0; i < n - 1; i++) {
 
    // Find no. of chocolates
    // lose or gain
    int choc = arr[i] - arr[i + 1];
 
    // Add into curr_coc
    curr_choc += choc;
 
    // if no. of chocolates becomes
    // negative that means we have
    // to buy that no. of chocolates
    if (curr_choc < 0) {
      choc_buy += abs(curr_choc);
      curr_choc = 0;
    }
  }
 
  // Return cost required
  return choc_buy * choc_cost;
}
 
// Drivers code
int main() {
  int arr[] = {10, 6, 11, 4, 7, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
 
  // Price of each candy
  int p = 5;
 
  cout << findMinCost(arr, n, p);
 
  return 0;
}

Java

// Java program to calculate
// minimum cost for candies
import java.io.*;
 
class GFG 
{
    // Function to find minimum cost
    // to be incurred
    static int findMinCost(int arr[], int n, int choc_cost) 
    {
     
    // To reach first station, initial
    // chocolates required
    int choc_buy = arr[0];
    int curr_choc = 0;
     
    // Start traversing
    for (int i = 0; i < n - 1; i++) 
    {
     
        // Find no. of chocolates
        // lose or gain
        int choc = arr[i] - arr[i + 1];
     
        // Add into curr_coc
        curr_choc += choc;
     
        // if no. of chocolates becomes
        // negative that means we have
        // to buy that no. of chocolates
        if (curr_choc < 0) 
        {
            choc_buy += Math.abs(curr_choc);
            curr_choc = 0;
        }
    }
     
    // Return cost required
    return choc_buy * choc_cost;
    }
     
    // Drivers code
    public static void main (String[] args) 
    {
        int arr[] = {10, 6, 11, 4, 7, 1};
        int n = arr.length;
         
        // Price of each candy
        int p = 5;
         
        System.out.println ( findMinCost(arr, n, p));   
    }
}
 
// This code is contributed by vt_m

Python3

# Python 3 program to calculate
# minimum cost for candies
 
# Function to find minimum cost
# to be incurred
def findMinCost(arr, n, choc_cost): 
 
    # To reach first station, 
    # initial chocolates required
    choc_buy = arr[0] 
    curr_choc = 0
 
    # Start traversing
    for i in range(0,n - 1): 
     
        # Find no. of chocolates lose
        # or gain
        choc = arr[i] - arr[i + 1] 
     
        # Add into curr_coc
        curr_choc += choc 
     
        # if no. of chocolates becomes
        # negative that means we have
        # to buy that no. of chocolates
        if (curr_choc < 0): 
            choc_buy += abs(curr_choc) 
            curr_choc = 0
     
    # Return cost required
    return choc_buy * choc_cost 
 
 
# Drivers code
arr = [10, 6, 11, 4, 7, 1] 
n = len(arr)
 
# Price of each candy
p = 5
 
print(findMinCost(arr, n, p))
 
# This code is contributed by Smitha Dinesh Semwal

C#

// C# program to calculate
// minimum cost for candies
using System;
 
class GFG 
{
    // Function to find minimum cost
    // to be incurred
    static int findMinCost(int []arr,
                    int n, int choc_cost) 
    {
         
        // To reach first station, initial
        // chocolates required
        int choc_buy = arr[0];
        int curr_choc = 0;
         
        // Start traversing
        for (int i = 0; i < n - 1; i++) 
        {
         
            // Find no. of chocolates
            // lose or gain
            int choc = arr[i] - arr[i + 1];
         
            // Add into curr_coc
            curr_choc += choc;
         
            // if no. of chocolates becomes
            // negative that means we have
            // to buy that no. of chocolates
            if (curr_choc < 0) 
            {
                choc_buy += Math.Abs(curr_choc);
                curr_choc = 0;
            }
    }
     
    // Return cost required
    return choc_buy * choc_cost;
    }
     
    // Drivers code
    public static void Main () 
    {
        int []arr = {10, 6, 11, 4, 7, 1};
        int n = arr.Length;
         
        // Price of each candy
        int p = 5;
         
    Console.WriteLine( findMinCost(arr, n, p)); 
    }
}
 
// This code is contributed by vt_m

PHP

<?php
// PHP program to calculate
// minimum cost for candies
 
// Function to find minimum cost
// to be incurred
function findMinCost($arr, $n, $choc_cost) 
{
 
    // To reach first station, initial
    // chocolates required
    $choc_buy = $arr[0];
    $curr_choc = 0;
     
    // Start traversing
    for ($i = 0; $i < $n - 1; $i++) {
     
        // Find no. of chocolates
        // lose or gain
        $choc = $arr[$i] - $arr[$i + 1];
     
        // Add into curr_coc
        $curr_choc += $choc;
     
        // if no. of chocolates becomes
        // negative that means we have
        // to buy that no. of chocolates
        if ($curr_choc < 0) {
        $choc_buy += abs($curr_choc);
        $curr_choc = 0;
        }
    }
     
    // Return cost required
    return $choc_buy * $choc_cost;
}
 
// Driver Code
$arr = array(10, 6, 11, 4, 7, 1);
$n = count($arr);
 
// Price of each candy
$p = 5;
 
echo findMinCost($arr, $n, $p);
 
// This code is contributed by Sam007
?>

Javascript

<script>
// Javascript program to calculate
// minimum cost for candies
 
 
// Function to find minimum cost
// to be incurred
function findMinCost(arr,  n,  choc_cost) {
 
// To reach first station, initial
// chocolates required
var choc_buy = arr[0];
var curr_choc = 0;
 
// Start traversing
for (var i = 0; i < n - 1; i++) {
 
    // Find no. of chocolates
    // lose or gain
    var choc = arr[i] - arr[i + 1];
 
    // Add into curr_coc
    curr_choc += choc;
 
    // if no. of chocolates becomes
    // negative that means we have
    // to buy that no. of chocolates
    if (curr_choc < 0) {
    choc_buy += Math.abs(curr_choc);
    curr_choc = 0;
    }
}
 
// Return cost required
return (choc_buy * choc_cost);
}
 
var  arr = [10, 6, 11, 4, 7, 1];
var n = 6;
 
// Price of each candy
var p = 5;
 
document.write(findMinCost(arr, n, p));
 
 
 
</script>

Output:

Time Complexity: O(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 zambiatek!