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
  • Piyush Sinha

    tc = int(input())

    for i in range(tc):

    M=int(input())

    N=int(input())

    flavour = [int(i) for i in input().split(‘ ‘)]

    flavourcopy = [i for i in flavour]

    flavour.sort()

    minm = 0

    maxm = len(flavour)-1

    while(flavour[minm]+flavour[maxm]!=M):

    if(flavour[minm]+flavour[maxm] > M):

    maxm -= 1

    else:

    minm += 1

    flavour_val_min = flavour[minm]

    flavour_val_max = flavour[maxm]

    flavour_orig = [str(i) for i in flavourcopy]

    minindex = flavour_orig.index(str(flavour_val_min)) + 1

    maxindex = flavour_orig.index(str(flavour_val_max)) + 1

    if(minindex==maxindex):

    maxindex +=1

    print(str(minindex) + ” ” + str(maxindex))

    Can you point out error in my code.
    Please

  • Stephen Milton

    I have a solution I believe is O(N).
    It is in C++.
    I created (tree) map with each cost as the key and a vector of indices as the value.
    Then I first checked whether M was even M/2 was a cost with at least two values. If so then that’s the answer.

    Otherwise, I set two iterators: bottom set to the lowest value in the map and top to the first value greater than M/2 (actually the initial values of the iterators don’t matter since they will both quickly change)
    The C++ map has a method called lower_bound which returns an iterator pointing to an element with a key greater than or equal to the key provided in lower bound.
    I used this method to alternately select a new value for the bottom and top iterators as follows:
    bottom = lower_bound(M-top_key) // we really the key less than or equal here so the adjustment
    top = lower_bound(M-bottom_key)

    This converges quickly (logN) to the solution.
    Since the each lower_bound call is a tree search, the search algorithm should O(log squared N).
    The reading of the data is by necessity O(N)

    int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int T;
    cin >> T;
    while ( T– > 0 ) {
    int M;
    int N;
    cin >> M >> N;
    map<int,vector> price;

    for ( int i = 1; i > flavor;

    if ( flavor < M ) {

    if ( price.count(flavor) == 0 )
    price[flavor] = vector(1,i);
    else
    price[flavor].push_back(i);
    }
    }

    int half = M/2;
    auto middle = price.lower_bound(half);
    auto bottom = price.begin();
    auto top = price.upper_bound(half);
    int one;
    int two;

    if ( 2*half == M && middle->first == half && middle->second.size() >= 2 ) {

    one = middle->second[0];
    two = middle->second[1];

    } else {
    while ( bottom != middle && top != price.end() ) {

    bottom = price.lower_bound(M – top->first);

    if ( bottom->first + top->first == M )
    break;
    else if ( bottom != price.begin() )
    bottom–;

    top = price.lower_bound(M – bottom->first);

    if ( bottom->first + top->first == M )
    break;
    }

    one = bottom->second[0];
    two = top->second[0];
    }

    if ( one < two )
    cout << one << ' ' << two << endl;
    else
    cout << two << ' ' << one << endl;
    }

    return 0;
    }

    • Hey Stephen,

      thanks for sharing.

      You are right, the solution is possible in better time than N^2. I like your clever use of lower_bound yet it makes it very hard to reason about the algorithm. I struggle to come up with a proof that it will actually terminate in all possible cases. Neither am I really sure what the runtime complexity is. It is log(N)-ish that for sure đŸ™‚

      The issue with this task is that HR does not provide enough test cases. While creating an updated solution based on the insight from your post, I screwed up, and they did not catch it.

      I translated your code into (slower) Python and updated the post.

      • Sidharth Samant

        Hi Martin. As far as I know, the sorted() function has O(nlogn) complexity. So if you’re using that inside the enumerate loop (which itself has O(n) complexity), wouldn’t that make it O(n^2logn) complexity for the whole program? Forgive me if I sound too silly, I’m not very good at calculating complexities.