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 incurredint 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 codeint 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 candiesimport 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 incurreddef 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 codearr = [10, 6, 11, 4, 7, 1] n = len(arr)# Price of each candyp = 5print(findMinCost(arr, n, p))# This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to calculate// minimum cost for candiesusing 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 incurredfunction 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 incurredfunction findMinCost(arr, n, choc_cost) {// To reach first station, initial// chocolates requiredvar choc_buy = arr[0];var curr_choc = 0;// Start traversingfor (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 requiredreturn (choc_buy * choc_cost);}var arr = [10, 6, 11, 4, 7, 1];var n = 6;// Price of each candyvar p = 5;document.write(findMinCost(arr, n, p));</script> |
Output:
55
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
