##### 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 *i*th 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. But I could not find anything better.

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.