Hash Tables: Ice Cream Parlor - Hacker Rank Solution

Check out the resources on the page's right side to learn more about binary search. The video tutorial is by Gayle Laakmann McDowell, author of the best-selling interview book Cracking the Coding Interview.

Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool their money to buy ice cream. On any given day, the parlor offers a line of flavors. Each flavor has a cost associated with it.

Given the value of  and the  of each flavor for  trips to the Ice Cream Parlor, help Sunny and Johnny choose two distinct flavors such that they spend their entire pool of money during each visit. ID numbers are the 1- based index number associated with a . For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second.

For example, there are  flavors having . Together they have  to spend. They would purchase flavor ID's  and  for a cost of . Use  based indexing for your response.

Note:

• Two ice creams having unique IDs  and  may have the same cost (i.e., ).
• There will always be a unique solution.

Function Description

Complete the function whatFlavors in the editor below. It must determine the two flavors they will purchase and print them as two space-separated integers on a line.

whatFlavors has the following parameter(s):

• cost: an array of integers representing price for a flavor
• money: an integer representing the amount of money they have to spend

Input Format

The first line contains an integer, , the number of trips to the ice cream parlor.

Each of the next  sets of  lines is as follows:

• The first line contains .
• The second line contains an integer, , the size of the array .
• The third line contains  space-separated integers denoting the .

Constraints

Output Format

Print two space-separated integers denoting the respective indices for the two distinct flavors they choose to purchase in ascending order. Recall that each ice cream flavor has a unique ID number in the inclusive range from  to .

Sample Input

2
4
5
1 4 5 3 2
4
4
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  dollars. There are five flavors available that day and flavors  and  have a total cost of .
2. The second time, they pool together  dollars. There are four flavors available that day and flavors  and  have a total cost of .

Hash Tables: Ice Cream Parlor - Hacker Rank Solution

Naive Solution

1. Run a nested loop where the first (outer) loop corresponds to the first flavor and the second (inner) loop corresponds to the second flavor.
2. Once the first valid solution is found (i.e., ), break the loop and print your answer.

// Naive C++ Solution

#include<bits/stdc++.h>
using namespace std;

void solve(vector<int>arr, int money){
    int n = arr.size();
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(arr[i]+arr[j] == money) {
                cout << i + 1 << " " << j + 1 << endl;
                break;
            }
        }
    }
}

int main(){
    int t;
    cin >> t;
    while(t--){

        int n, money;
        cin >> money >> n;

        vector<int>arr(n);
        for(int i = 0; i < n; i++)
            cin >> arr[i];

        solve(arr, n);
    }
    return 0;
}

The complexity for this is , which will time out if the data sets are large.

Optimized solution using Hash Table

1. Loop over the  array.
2. Consider two distinct flavors having costs  and . Because Sunny and Johnny want to spend all  dollars during each trip to the store, we know that  for the correct solution. From this, we can say that if we have some first flavor with cost , it can only be paired with flavor . If we find the  satisfying that equation in the  array, then we have our answer. We determine this by checking if  exists in the  array; if it does, then we have our answer. If  does not exist in the  array, then we simply check the next possible .

Note: The cost of the two flavors may be the same! In that case, you must make sure that the cost occurs twice (i.e., ).

In C++, the problem can be solved by using std::map.The time complexity of such a solution is .

Solution using Binary Search

You may refer the video tutorial for a binary search based solution.

Problem Tester's code:

#include<bits/stdc++.h>
using namespace std;

map<int,int>mp;

void solve(vector<int>arr, int money){
    int n = arr.size();
    int ans1 = -1, ans2 = -1;
    for(int i = 0; i < n; i++) {
        int v1 = arr[i], v2 = money - v1;
        if(v1 != v2) {
         // if both elements are present in map
            if(mp.count(v1) && mp.count(v2)) {
                ans1 = v1;
                ans2 = v2;
                break;
            }
        } 
        else{
          // count of the element must be greater than 1 if they are same
                if(mp[v1] > 1){
                    ans1 = v1;
                    ans2 = v1;
                    break;
                }
        }
    }

    set<int>s;
    for(int i = 0; i < n; i++){
        if(arr[i] == ans1 || arr[i] == ans2)
            s.insert(i);
    }

    for(int it:s)
        cout << it + 1 << " ";
    cout << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        mp.clear();
        int n, money;
        cin >> money >> n;

        vector<int>arr(n);
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
            // hashed the occurence of each amount with its frequency
            mp[arr[i]]++;
        }

        solve(arr, money);
    }
    return 0;
}