##### Short Problem Definition:

Sunny and Johnny together have M dollars they want to spend on ice cream. The parlor offers N flavors, and they want to choose two flavors so that they end up spending the whole amount.

You are given the cost of these flavors. The cost of the ith flavor is denoted by ci. You have to display the indices of the two flavors whose sum is M.

##### Link

##### Complexity:

time complexity is O(n)

space complexity is O(1)

##### Execution:

I genuinely don’t like n^2 solutions. They scream for a better way. For this task, I struggled to find a better one. Binary search won’t work because of the possible duplicates. Especially special cases where every element is the same and M is double this element. You have to generate all combinations anyways (which is n^2 pairs).

UPDATE(18/05/16): I found an O(N) solution. As always the complexity of the hash-map can be disputed. I prefer tree-maps which would give us a guaranteedÂ runtime complexity of O(N*log(N)).

##### Solution:

#!/usr/bin/py def icecream(flavors, M): # O(N) complexity flavor_map = {} for idx, flavor in enumerate(flavors): residual = (M - flavor) if residual in flavor_map: return sorted([flavor_map[residual], idx]) if not flavor in flavor_map: flavor_map[flavor] = idx if __name__ == '__main__': t = input() for _ in xrange(t): m = input() n = input() flavors = map(int, raw_input().split()) result_arr = icecream(flavors, m) print result_arr[0]+1, result_arr[1]+1

#!/usr/bin/py def icecream(flavors, M): # O(N^2) complexity for idx in xrange(len(flavors)-1): for idx2 in xrange(idx+1, len(flavors)): if flavors[idx] + flavors[idx2] == M: return [idx+1, idx2] if __name__ == '__main__': t = input() for _ in xrange(t): m = input() n = input() flavors = map(int, raw_input().split()) result_arr = icecream(flavors, m) print result_arr[0]+1, result_arr[1]+1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.