# 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[0] + 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.

### 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  int t; cin >> t; int n, m, f; 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 0 && freq[x] > (x == p[i])) // > 1 if x == p[i] { auto index = find(begin(p), next(begin(p), i), x); if (index == next(begin(p), i)) index = find(next(begin(p), i + 1), end(p), x); auto first = (int)(distance(begin(p), index)+1); auto second = i+1; cout << min(first, second) << " " << max(first, second) << "\n"; break; } } } 

Two notes:

• the particular condition freq[x] > (x == p[i]) is just syntactic sugar to say “if x is p[i] then I need one value more in the frequency table since the first one is for p[i], so I need at least 2. Otherwise, 1 is ok”;
• we divide searching the vector into two parts: first, from the beginning to i excluded and, possibly, from i + 1 to the end. This way we still use find without extra logic nor custom lambdas. The idea is just to avoid finding p[i] when x == p[i].
comments powered by Disqus