# Find the minimum and maximum amount to buy all N candies

In a candy store there are N different types of candies available and the prices of all the N different types of candies are provided. There is also an attractive offer by candy store. We can buy a single candy from the store and get at-most K other candies (all are different types) for free.

1. Find minimum amount of money we have to spend to buy all the N different candies.
2. Find maximum amount of money we have to spend to buy all the N different candies.

In both the cases we must utilize the offer and get maximum possible candies back. If k or more candies are available, we must take k candies for every candy purchase. If less than k candies are available, we must take all candies for a candy purchase.

Examples:

```Input :  price[] = {3, 2, 1, 4}
k = 2
Output :  Min = 3, Max = 7
Since k is 2, if we buy one candy we can take
So in the first case we buy the candy which
costs 1 and take candies worth 3 and 4 for
free, also you buy candy worth 2 as well.
So min cost = 1 + 2 = 3.
In the second case we buy the candy which
costs 4 and take candies worth 1 and 2 for
free, also We buy candy worth 3 as well.
So max cost = 3 + 4 = 7.
```

One important thing to note is, we must use the offer and get maximum candies back for every candy purchase. So if we want to minimize the money, we must buy candies of minimum cost and get candies of maximum costs for free. To maximize the money, we must do reverse. Below is algorithm based on this.

```First Sort the price array.

For finding minimum amount :
and reduce k free candies from last with
every single purchase.

For finding maximum amount :
Start purchasing candies from the end
and reduce k free candies from starting
in every single purchase.
```

## C++

 `// C++ implementation to find the minimum ` `// and maximum amount ` `#include ` `using` `namespace` `std; ` ` `  `// Function to find the minimum amount ` `// to buy all candies ` `int` `findMinimum(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``int` `res = 0; ` `    ``for` `(``int` `i=0; i=index; i--) ` `    ``{ ` `        ``// Buy candy with maximum amount ` `        ``res += arr[i]; ` ` `  `        ``// And get k candies for free from ` `        ``// the starting ` `        ``index += k; ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {3, 2, 1, 4}; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` `    ``int` `k = 2; ` `    ``sort(arr, arr+n); ` ` `  `    ``cout << findMinimum(arr, n, k)<<``" "` `         ``<< findMaximum(arr, n, k)<

## Java

 `// Java implementation to find the  ` `// minimum and maximum amount ` `import` `java.util.*; ` ` `  `class` `GFG { ` ` `  `    ``// Function to find the minimum  ` `    ``// amount to buy all candies ` `    ``static` `int` `findMinimum(``int` `arr[], ``int` `n, ``int` `k) ` `    ``{ ` `        ``int` `res = ``0``; ` `        ``for` `(``int` `i = ``0``; i < n; i++)  ` `        ``{ ` `            ``// Buy current candy ` `            ``res += arr[i]; ` ` `  `            ``// And take k candies for free ` `            ``// from the last ` `            ``n = n - k; ` `        ``} ` `        ``return` `res; ` `    ``} ` ` `  `    ``// Function to find the maximum  ` `    ``// amount to buy all candies ` `    ``static` `int` `findMaximum(``int` `arr[], ``int` `n, ``int` `k) ` `    ``{ ` `        ``int` `res = ``0``, index = ``0``; ` ` `  `        ``for` `(``int` `i = n - ``1``; i >= index; i--)  ` `        ``{ ` `            ``// Buy candy with maximum amount ` `            ``res += arr[i]; ` ` `  `            ``// And get k candies for free from ` `            ``// the starting ` `            ``index += k; ` `        ``} ` `        ``return` `res; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = { ``3``, ``2``, ``1``, ``4` `}; ` `        ``int` `n = arr.length; ` `        ``int` `k = ``2``; ` `        ``Arrays.sort(arr); ` ` `  `        ``System.out.println(findMinimum(arr, n, k) +  ` `                          ``" "` `+ findMaximum(arr, n, k)); ` `    ``} ` `} ` ` `  `// This code is contributed by prerna saini `

## Python3

 `# Python implementation ` `# to find the minimum ` `# and maximum amount ` ` `  `# Function to find ` `# the minimum amount ` `# to buy all candies ` `def` `findMinimum(arr,n,k): ` ` `  `    ``res ``=` `0` `    ``i``=``0` `    ``while``(n): ` `     `  `        ``# Buy current candy ` `        ``res ``+``=` `arr[i] ` `  `  `        ``# And take k ` `        ``# candies for free ` `        ``# from the last ` `        ``n ``=` `n``-``k ` `        ``i``+``=``1` `    ``return` `res ` `  `  `# Function to find ` `# the maximum amount ` `# to buy all candies ` `def` `findMaximum(arr, n, k): ` ` `  `    ``res ``=` `0` `    ``index ``=` `0` `    ``i``=``n``-``1` `    ``while``(i>``=``index): ` `     `  `        ``# Buy candy with ` `        ``# maximum amount ` `        ``res ``+``=` `arr[i] ` `  `  `        ``# And get k candies ` `        ``# for free from ` `        ``# the starting ` `        ``index ``+``=` `k ` `        ``i ``-``=` `1` ` `  `    ``return` `res ` `  `  `# Driver code ` ` `  `arr ``=` `[``3``, ``2``, ``1``, ``4``] ` `n ``=` `len``(arr) ` `k ``=` `2` ` `  `arr.sort() ` `  `  `print``(findMinimum(arr, n, k),``" "``, ` `    ``findMaximum(arr, n, k)) ` ` `  `# This code is contributed ` `# by Anant Agarwal. `

/div>

## C#

 `// C# implementation to find the  ` `// minimum and maximum amount ` `using` `System; ` `         `  `public` `class` `GFG { ` `     `  `    ``// Function to find the minimum  ` `    ``// amount to buy all candies ` `    ``static` `int` `findMinimum(``int` `[]arr,  ` `                         ``int` `n, ``int` `k) ` `    ``{ ` `        ``int` `res = 0; ` `        ``for` `(``int` `i = 0; i < n; i++)  ` `        ``{ ` `             `  `            ``// Buy current candy ` `            ``res += arr[i]; ` ` `  `            ``// And take k candies for ` `            ``// free from the last ` `            ``n = n - k; ` `        ``} ` `         `  `        ``return` `res; ` `    ``} ` ` `  `    ``// Function to find the maximum  ` `    ``// amount to buy all candies ` `    ``static` `int` `findMaximum(``int` `[]arr, ` `                          ``int` `n, ``int` `k) ` `    ``{ ` `        ``int` `res = 0, index = 0; ` ` `  `        ``for` `(``int` `i = n - 1; i >= index; i--)  ` `        ``{ ` `            ``// Buy candy with maximum ` `            ``// amount ` `            ``res += arr[i]; ` ` `  `            ``// And get k candies for free ` `            ``// from the starting ` `            ``index += k; ` `        ``} ` `         `  `        ``return` `res; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = { 3, 2, 1, 4 }; ` `        ``int` `n = arr.Length; ` `        ``int` `k = 2; ` `        ``Array.Sort(arr); ` ` `  `        ``Console.WriteLine( ` `          ``findMinimum(arr, n, k) + ``" "` `             ``+ findMaximum(arr, n, k)); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007. `

## PHP

 `= ``\$index``; ``\$i``--) ` `    ``{ ` `         `  `        ``// Buy candy with maximum amount ` `        ``\$res` `+= ``\$arr``[``\$i``]; ` ` `  `        ``// And get k candies ` `        ``// for free from ` `        ``// the starting ` `        ``\$index` `+= ``\$k``; ` `    ``} ` `    ``return` `\$res``; ` `} ` ` `  `    ``// Driver Code ` `    ``\$arr` `= ``array``(3, 2, 1, 4); ` `    ``\$n` `= sizeof(``\$arr``); ` `    ``\$k` `= 2; ` `    ``sort(``\$arr``); sort(``\$arr``,``\$n``); ` ` `  `    ``echo` `findMinimum(``\$arr``, ``\$n``, ``\$k``),``" "` `            ``,findMaximum(``\$arr``, ``\$n``, ``\$k``); ` `    ``return` `0; ` ` `  `// This code is contributed by nitin mittal. ` `?> `

Output:

```3 7
```

Time Complexity : O(n log n)

## tags:

Greedy Sorting Greedy Sorting