HackerRank ‘Ice Cream Parlor’ Solution

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

Ice Cream Parlor

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.

Facebooktwittergoogle_plusredditpinterestlinkedin