HackerRank Hash Tables: Ice Cream Parlor solution in python

This is solution for HackerRank Hash Tables: Ice Cream Parlor challenge, in python. This is a problem in the Interview Preparation Kit > Search Algorithms and is considered of medium difficulty.

The problem

The problem is simple: 2 friends want to buy ice cream and they must spend all their money each trip. some rules:

• Every flavor has a different value.
• They must choose the flavors (numbered) to sum up to money they have
• they can't buy the same flavor
• You need to return the index starting by 1 (not 0)

The naive solution

The naive solution is to traverse the entire set almost twice. Almost because for friend 2 we will traverse only the positions not chose yet

# inefficient, naive solution: O(n²) def whatFlavors_inneficient(cost, money): for i1, c1 in enumerate(cost, 1): for i2, c2 in enumerate(cost[i1:], i1 + 1): if (c1 + c2) == money: print(i1, i2) return 

The final solution

In the final solution, we must trade time for space, creating a dictionary. The reason is to find, after we spend the money on the first ice cream, if there is another flavor to sum up to the money we got there.

 # cost: [1, 4, 5, 3, 2]  dcost = dict(enumerate([c for c in cost], 1)) # {1: 1, 2: 4, 3: 5, 4: 3, 5: 2}  dcost = {v: k for k, v in dcost.items()} # {1: 1, 4: 2, 5: 3, 3: 4, 2: 5} 

So, we still need to traverse all the flavors, but just once.

The complete solution is as follows

def whatFlavors(cost, money): # inverted (v,k) dictionary of costs  # to find easily the value that complements the first iteration  dcost = dict(enumerate([c for c in cost], 1)) dcost = {v: k for k, v in dcost.items()} # traverse once  for i1, c1 in enumerate(cost, 1): # the cost of second ice cream must be  c2 = money - c1 i2 = dcost.get(c2) # if found, return  if i2 and (i2 != i1): print(i1, i2) return