Maximum number of candies that can be bought
Given an array arr[] of size n where arr[i] is the number of candies of type i. You have an unlimited amount of money. The task is to buy as many candies as possible satisfying the following conditions:
If you buy x(i) candies of type i (clearly, 0 ? x(i) ? arr[i]), then for all j (1 ? j ? i) at least one of the following must hold:
- x(j) < x(i) (you bought less candies of type j than of type i)
- x(j) = 0 (you bought 0 candies of type j)
Examples:
Input:arr[] = {1, 2, 1, 3, 6}
Output: 10
x[] = {0, 0, 1, 3, 6} where x[i] is the number of candies bought of type i
Input: arr[] = {3, 2, 5, 4, 10}
Output: 20
Input: arr[] = {1, 1, 1, 1}
Output: 1
Approach: We can use a greedy approach and start from the end of the array. If we have taken x candies of type i + 1 then we can only take min(arr[i], x – 1) candies of type i. If this value is negative, we cannot buy candies of the current type.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum candies // that can be bought int maxCandies( int arr[], int n) { // Buy all the candies of the last type int prevBought = arr[n - 1]; int candies = prevBought; // Starting from second last for ( int i = n - 2; i >= 0; i--) { // Amount of candies of the current // type that can be bought int x = min(prevBought - 1, arr[i]); if (x >= 0) { // Add candies of current type // that can be bought candies += x; // Update the previous bought amount prevBought = x; } } return candies; } // Driver code int main() { int arr[] = { 1, 2, 1, 3, 6 }; int n = sizeof (arr) / sizeof (arr[0]); cout << maxCandies(arr, n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the maximum candies // that can be bought static int maxCandies( int arr[], int n) { // Buy all the candies of the last type int prevBought = arr[n - 1 ]; int candies = prevBought; // Starting from second last for ( int i = n - 2 ; i >= 0 ; i--) { // Amount of candies of the current // type that can be bought int x = Math.min(prevBought - 1 , arr[i]); if (x >= 0 ) { // Add candies of current type // that can be bought candies += x; // Update the previous bought amount prevBought = x; } } return candies; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 1 , 3 , 6 }; int n = arr.length; System.out.println(maxCandies(arr, n)); } } // This code is contributed by Code_Mech. |
Python3
# Python3 implementation of the approach # Function to return the maximum candies # that can be bought def maxCandies(arr, n) : # Buy all the candies of the last type prevBought = arr[n - 1 ]; candies = prevBought; # Starting from second last for i in range (n - 2 , - 1 , - 1 ) : # Amount of candies of the current # type that can be bought x = min (prevBought - 1 , arr[i]); if (x > = 0 ) : # Add candies of current type # that can be bought candies + = x; # Update the previous bought amount prevBought = x; return candies; # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 1 , 3 , 6 ]; n = len (arr) print (maxCandies(arr, n)); # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum candies // that can be bought static int maxCandies( int [] arr, int n) { // Buy all the candies of the last type int prevBought = arr[n - 1]; int candies = prevBought; // Starting from second last for ( int i = n - 2; i >= 0; i--) { // Amount of candies of the current // type that can be bought int x = Math.Min(prevBought - 1, arr[i]); if (x >= 0) { // Add candies of current type // that can be bought candies += x; // Update the previous bought amount prevBought = x; } } return candies; } // Driver code public static void Main() { int [] arr= { 1, 2, 1, 3, 6 }; int n = arr.Length; Console.WriteLine(maxCandies(arr, n)); } } // This code is contributed by Code_Mech. |
PHP
<?php // PHP implementation of the approach // Function to return the maximum candies // that can be bought function maxCandies( $arr , $n ) { // Buy all the candies of the last type $prevBought = $arr [ $n - 1]; $candies = $prevBought ; // Starting from second last for ( $i = $n - 2; $i >= 0; $i --) { // Amount of candies of the current // type that can be bought $x = min( $prevBought - 1, $arr [ $i ]); if ( $x >= 0) { // Add candies of current type // that can be bought $candies += $x ; // Update the previous bought amount $prevBought = $x ; } } return $candies ; } // Driver code $arr = array (1, 2, 1, 3, 6 ); $n = sizeof( $arr ); echo (maxCandies( $arr , $n )); // This code is contributed by Code_Mech. ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximum candies // that can be bought function maxCandies(arr, n) { // Buy all the candies of the last type let prevBought = arr[n - 1]; let candies = prevBought; // Starting from second last for (let i = n - 2; i >= 0; i--) { // Amount of candies of the current // type that can be bought let x = Math.min(prevBought - 1, arr[i]); if (x >= 0) { // Add candies of current type // that can be bought candies += x; // Update the previous bought amount prevBought = x; } } return candies; } // Driver Code let arr = [ 1, 2, 1, 3, 6 ]; let n = arr.length; document.write(maxCandies(arr, n)); </script> |
10
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us