See the original problem on HackerRank.
Solutions
A simple solution consists in sorting both sequences and running two nested for loops to calculate the possible costs. Although this solution is \(O((n+m) \cdot log(n+m)) + n \cdot m)\), it’s acceptable since the input is small:


Linqbased solution, with cartesian product (by fabrizio_sanmar1):


Optimized solution: \(O(n+m (log (n+m))\)
If we sort the first sequence in descending and the other in ascending order we only have to visit each element once, because we can make use of the fact that the sum of the element following the current will be greater/less than the current sum depending on the direction we iterate from:


Binary search on the array of all possible costs (not a cheaper solution)
Maurizio Carli and his coding partner proposed this variation:
 create an array with all possible costs
 sort such an array
 use binary search to find the first element not greater than the budget
Clearly, this solution is slower than the optimized one. It’s instructive to see how all the patterns are combined, though:


It’s interesting to note the usage of lower_bound
: since lower_bound
returns the first element greater than or equal to another one, by default it may return a value that is greater than the budget. We could just check if this happens and return the previous element in case. But we can stress the pattern a bit more to learn something new. If we run lower_bound
backwards we find the first element less than or equal to our budget! It’s just the matter of iterating backwards (with reverse iterators) and adapt lower_bound
to work with a descendingsorted sequence (that’s why we use greater
).