Store Credit Problem from Google Code Jam

scp.py

def store_credit_problem(credit, items):
  """
  @author: Dairon Medina <http://github.com/codeadict>
  
  My python implementation for Store Credit Problem from Google Code Jam:
  http://code.google.com/codejam/contest/351101/dashboard#s=p0
  @param credit: integer representing store credit
  @param items: list of product prices, must be integers
  @returns: tuple with the two prices that consumes the whole credit
  
  Usage:
    >>> store_credit_problem(100,[5, 30, 75, 40, 25])
    (3, 5)
  """
  assert type(credit) == int
  assert type(items) == list
  d = {}
  # Iterate all the items and add it as price: index, where price is a set to not repeat it
  for index, price in enumerate(items):
    d[price] = d.get(price, set())
    d[price].add(index + 1)
    
  # Now iterate the dict 
  for price in d.keys():
    if price <= credit:
      price_sample = d[price].pop() # remove the price index from dict and take as a test sample
      # now see if some complementary value with price  fills the credit
      if credit - price in d:
        complementary_price = d[credit - price].pop()
        # Tada we found a pair of prices to spend all the money
        return min(price_sample, complementary_price), max(price_sample, complementary_price)
      # No solution found on this iteration so lets back the price_sample to dict, maybe it plays nice with other value
      d[price].add(price_sample)
  # show a message if problem cant be solved
  return "Sorry, there are no products to spend %d credit, maybe you have to give some part to the shop again :(" % credit

First have done a double iteration on all items on list and sum the values but this was slower and not optimized when items list is big, the complexity is always quadratic O(n^2) so i made a new version as checked https://wiki.python.org/moin/TimeComplexity and saw dictionary and set operations are constant O(n) and now its faster , ending with O(n) complexity.

Here are the 2 versions, u can run using python cProfiler to check times and number of calls like:

 >>> import cProfile 
... cProfile.run('store_credit_problem(10, [1,2,4,3,10,4,5,6,6,10,23,56,4,1,1,3,5,2,3,7,4,9,2,8,3,5,1,9,37,84,84,3])')