We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Ice Cream Parlor
  5. Discussions

Ice Cream Parlor

  • sayantanmaiti
     + 0 comments

    Spoiler Answer (Please try solving it yourself)

    Simplest way I did it was to search the 2 elements using binary search in a sorted array, and then finding these 2 elements using linear search.

    Managing duplicates is a little tricky, I just incremented the second index by 1 if they both indexes are equal.

    There may be a more efficient solution.

    int binS(vector<int> arr, int l, int r, int x)
{
    while (l <= r)
    {
        int m = (l+r)/2;

        if (arr[m] == x)
            return 1;     // return true if found

        if (arr[m] < x)
            l = m + 1;

        else
            r = m - 1;
    }

    return -1;
}

vector <int> icecreamParlor(int m, vector <int> arr) {
    vector <int> orig = arr;
    vector <int> res;
    int left, right, find, equal = 0, found1 = 0, found2 = 0;
    sort(arr.begin(), arr.end());
    for (int i = 0; i<arr.size() - 1; i++){
        left = arr[i];
        find = abs(m - arr[i]);
        right = binS(arr, i, arr.size(), find);
        if (right != -1) {
            if (left == find)
                equal = 1;
            else
                equal = 0;
            for (int i = 0; i<orig.size();i++) {
                
                if (orig[i] == left) {
                    res.push_back(i + 1);
                    found1 = 1;
                }
                if (orig[i] == find) {
                    res.push_back(i + 1 + equal); // increment second index by 1 if they are of the same element
                    found2 = 1;
                }
                if (found1 && found2) // break loop if both are found
                    break;
            }
            break;
        }
        else 
            continue;
    }
    return res;    
}