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. 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.

Facebooktwittergoogle_plusredditpinterestlinkedin