HackerRank Python Solution - Search Algorithm - Ice Cream Parlor

• Two friends like to pool their money and go to the ice cream parlor. They always choose two distinct flavors and they spend all of their money. 
• Given a list of prices for the flavors of ice cream, select the two that will cost all of the money they have. 
• Example. m = 6 cost = [1,3,4,5,6]
• The two flavors that cost 1 and 5 meet the criteria. Using 1-based indexing, they are at indices 1  and 4. 

Function Description:

• icecreamParlor has the following parameter(s): 
• int m: the amount of money they have to spend 
• int cost[n]: the cost of each flavor of ice cream 

Returns:

• int[2]: the indices of the prices of the two flavors they buy, sorted ascending

Input Format:

• The first line contains an integer, t, the number of trips to the ice cream parlor. The next t sets of lines each describe a visit. 
• Each trip is described as follows: 
1. The integer m, the amount of money they have pooled. 
2. The integer n, the number of flavors offered at the time.
3. n space-separated integers denoting the cost of each flavor: cost[cost[1], cost[2],..., cost[n]].

Note:

• The index within the cost array represents the flavor of the ice cream purchased.

Constraints:

• 1 ≤ t ≤ 50
• 2 ≤ m ≤ 10⁴
• 2 ≤ n ≤ 10⁴
• 1 ≤ cost[i] ≤ 10⁴, ∀ i Є [1, n]
• There will always be a unique solution.

Sample Input:

STDIN       Function
-----       --------
2           t = 2
4           k = 4
5           cost[] size n = 5
1 4 5 3 2   cost = [1, 4, 5, 3, 2]
4           k = 4
4           cost[] size n = 4
2 2 4 3     cost=[2, 2,4, 3]

Sample Output:

1 4
1 2

Explanation:

• Sunny and Johnny make the following two trips to the parlor:
1. The first time, they pool together m = 4 dollars. Of the five flavors available that day, flavors 1 and 4 have a total cost of 1+3 = 4.
2. The second time, they pool together m = 4 dollars. Of the four flavors available that day, flavors 1 and 2 have a total cost of 2+2 = 4.

Solution:

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'icecreamParlor' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER m
#  2. INTEGER_ARRAY arr
#

def icecreamParlor(m, arr):
    
    # Create a dictionary to store the indices of elements
    indices_dict = {}

    for i, cost in enumerate(arr):
        complement = m - cost
        # Check if the complement has been seen before
        if complement in indices_dict:
            return [indices_dict[complement] + 1, i + 1]
        # Store the current element's index
        indices_dict[cost] = i
        

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        m = int(input().strip())

        n = int(input().strip())

        arr = list(map(int, input().rstrip().split()))

        result = icecreamParlor(m, arr)

        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')

    fptr.close()

This solution uses a single pass through the array, and the dictionary lookups have an average time complexity of O(1). Therefore, the overall time complexity is reduced to O(N), making the solution more efficient.

Note: The problem statement is given by hackerrank.com but the solution is generated by the Geek4Tutorial admin. We highly recommend you solve this on your own, however, you can refer to this in case of help. If there is any concern regarding this post or website, please contact us using the contact form. Thank you!