Store Credit
Here's the store credit problem from Google Code Jam Qualification Round Africa 2010, which i discovered via Programming Praxis:
You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first). For instance, with C=100 and L={5,75,25} the solution is 2,3; with C=200 and L={150,24,79,50,88,345,3} the solution is 1,4; and with C=8 and L={2,1,9,4,4,56,90,3} the solution is 4,5.
Algorithm 1
Brute force. Test all pairs in the list. O(n^2) time and O(n) space.
Algorithm 2
Sort the list and then iterate over the list, at each step looking for the complementary price of the current price via binary search. O(n lg n) time and O(n) space.
Algorithm 3
Store the prices and indices in a dictionary and then iterate over the dictionary, at each step looking for the complementary price. Since dictionary look-up is constant time on average, this is an O(n) time (in the average case) and O(n) space algorithm. Hooray!
Here's a Python 2.7 implementation:
def find_pair(credit, prices):
# Make a dictionary with items of the form
# (price, set of indices of items with that price).
# Note that the price list could contain duplicate prices.
d = dict()
for (i, p) in enumerate(prices):
d[p] = d.get(p, set())
d[p].add(i + 1) # + 1 to index from 1 instead of 0.
for price in d.keys():
if price <= credit:
# Remove price index from d.
i = d[price].pop()
# Check whether there's a complementary price in d.
if credit - price in d:
# This works even if price == credit - price.
j = d[credit - price].pop()
return min(i, j), max(i, j)
# Reinsert price index into d.
d[price].add(i)
return "Sorry, no pair of item costs sum to %s" % credit
Why no comments? Public comments take too much time to moderate and maintain, time better spent playing outside, but you can still email me private comments by clicking the 'Comment' link above.