Daily bit(e) of C++ | Maximum ice cream purchase
Daily bit(e) of C++ #149, Common interview problem: maximum ice cream purchase.
Today we will look at a common interview problem: maximum ice cream.
Given an ice cream shop inventory as an array of positive integers representing costs, return the maximum number of items you can buy, given an amount of money.
Assume that the range of costs is comparable to or less than the total number of items, and implement an O(n) solution.
For example, for the inventory {1,6,3,2,5,4} and 10 money, we can purchase four items: {1,2,3,4}.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/6njqed3qj.
Solution
The maximum can be reached easily by spending in the order of cost. If we first buy the cheaper items, we will end up with the maximum number of items.
The obvious solution would be to sort the inventory and scan it in non-decreasing order, spending our money as we go. However, sorting would be O(n*log(n)) time complexity.
We have additional information, notably that the cost range is comparable to the number of elements. Therefore we can do a counting sort, meaning that instead of sorting the elements, we store the count of each element on the matching index.
This data structure will be good enough for our scan. As we scan, we can spend as much money as possible at each non-zero index.
