Easy Explanation , Binary search Approach 🔥⬆️
Approach\n1. Brute Force approach to solve this problem is to use a nested loop, where the outer loop iterates over the "spells" vector and the inner loop itera
# Approach\n1. Brute Force approach to solve this problem is to use a **nested loop**, where the outer loop iterates over the "spells" vector and the inner loop iterates over the "potions" vector. For each pair (s, p), the product s * p is checked against the target. If the product is greater than or equal to the target, then the pair is considered successful and the count is incremented.\nHowever, this approach has a time complexity of **O(n^2)**, which is inefficient for large values of n.\n2. A more efficient approach is to first sort the "potions" vector in non-decreasing order. This allows us to perform ***binary search*** on the sorted "potions" vector to ***find the index of the last element*** that satisfies the condition ***s * p >= target*** for a given s->element.\n Then, for each element s in the "spells" vector, we can use binary search to find the number of elements in the "potions" vector that satisfy the condition s * p >= target. This can be done by finding the index of the last element in the "potions" vector that satisfies the condition using binary search, and subtracting this index from the total number of elements in the "potions" vector.\n\n# Complexity\n- Time complexity:    O(n log n)\n- Space Complexity:   O(n)\n# Code\n```\nclass Solution {\npublic:\n    int getPairCount(vector<int>& potions, int& spell, long long& target)\n    {\n        int n = potions.size(), bestIdx = n;\n        int low = 0, high = n - 1;\n        \n        while(low <= high)\n        {\n            int mid = low + (high - low) / 2;\n            long long product = (long long)spell * potions[mid];\n            \n            if (product >= target)\n            {\n                bestIdx = mid;\n                high = mid - 1;\n            }\n            else low = mid + 1;\n        }\n       \n        return (n - bestIdx);\n    }\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success)\n    {\n        int n = spells.size();\n        vector<int>v(n);\n        sort(potions.begin(), potions.end());\n        for (int i = 0; i < n; i++) \n            ans[i] = getPairCount(potions, spells[i], success);\n        \n        return v;\n    }\n};\n```
['Array', 'Two Pointers', 'Binary Search', 'Sorting', 'C++']