# Ice Cream Parlor

See the original problem on HackerRank.

## Solutions

The brute force approach is easy: just run two nested loops and for each value $$x$$ find if it exists a value equals to $$target - x$$. This solution is quadratic.

Efficient solutions are based either on sorting or additional storage (e.g. frequency table, hash maps).

### A sort-based solution

Suppose we sort the prices $$p$$ in ascending order. Consider the sum $$p + p[n-1]$$ where $$n$$ is the number of available prices. If this sum was less than $$m$$, then we should increment the left hand index (we need to “pay more”). On the other hand, if the sum was greater than $$m$$, then we should decrement the right hand index (we need to “pay less”). This leads to the following solution based on 2-pointer technique:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33  int t; cin >> t; int n, m, f; while (t--) { cin >> m >> n; vector> v(n); for (auto i=0; i> f; v[i] = {f, i+1}; } sort(begin(v), end(v)); auto head = begin(v); auto tail = prev(end(v)); while (true) { if (head->first + tail->first > m) { tail--; } else if (head->first + tail->first < m) { head++; } else { cout << min(head->second, tail->second) << " " << max(head->second, tail->second) << "\n"; break; } } } 

Clearly, some additional storage is needed to sort the array without losing the original indexes.

The overall complexity is $$O(N \cdot logN$$ but it can be even optimized by using a linear-time sorting algorithm since the domain is small (e.g. counting sort or radix sort).

### Lookup-efficient data structures solutions

Another approach consists in using a multimap (since duplicates are possible) to lookup every value efficiently:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  int t; cin >> t; int n, m, f; while (t--) { cin >> m >> n; unordered_multimap flavors; for (auto i=0; i> f; flavors.emplace(f, i+1); } for (auto i : flavors) { auto it = flavors.find(m-i.first); if (it != end(flavors) && it->second != i.second) { cout << min(i.second, it->second) << " " << max(i.second, it->second) << "\n"; break; } } } 

A variation of this approach consists in using a frequency table. In this case, we do not keep track of the indexes with a sort of trick: when we find the matching price ($$m - p[i]$$), we just scan the array to find its position. Since this operation is perfomed only once, the solution stays linear:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27  int t; cin >> t; int n, m; while (t--) { cin >> m >> n; array freq{}; vector p(n); copy_n(istream_iterator(cin), n, begin(p)); for (auto i : p) freq[i]++; for (auto i=0; i 1 if x == p[i] (duplicate handling) if (x > 0 && freq[x] > (x == p[i])) { auto it = find(begin(p), end(p), x); if (it == next(begin(p), i)) // found the very same element it++; auto first = (int)(distance(begin(p), it)+1); auto second = i+1; cout << min(first, second) << " " << max(first, second) << "\n"; break; } } } 

Note that the weird condition freq[x] > (x == p[i]) is just syntactic sugar to say “if x is p[i] then we need to have at least two of such values available. For example, suppose we have:

 1  2, 2, 3, 5 

and suppose we need to find the indexes for k=4. When we check for the first 2, we have:

 1 2  const auto x = m - p[i]; // x = 4 - 2 = 2 if (2 > 0 && freq > (2 == 2)) // true, since freq = 2 
We've worked on this challenge in these gyms: modena