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<pair<int, int>> v(n);
    for (auto i=0; i<n; ++i)
    {
        cin >> 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<int, int> flavors;
    for (auto i=0; i<n; ++i)
    {
        cin >> 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<int, 100'000+1> freq{};
    vector<int> p(n);
    copy_n(istream_iterator<int>(cin), n, begin(p));
    for (auto i : p)
        freq[i]++;

    for (auto i=0; i<n; ++i)
    {
        auto x = m - p[i];
        if (x > 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