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