Simple 14 lines of code in O(n logn)✔
NOTE:\nPlease go through the Intution and Approach before jumping to the code. You will definitely get it!\nSuggested to write things on notebook while reading.
# NOTE:\n**Please go through the Intution and Approach before jumping to the code. You will definitely get it!**\nSuggested to write things on notebook while reading.\n\n# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn the question, we can see a basic pattern that we have to search a value for every element in spell. If we do this searching linearly for all n elements of spell (m times).\n\nIt will give us complexity of `O(n*m)`. This complexity can be reduced to  `O(n * logm)`  by using binary search. But before that we have to sort the array potions.\n```C++ []\nsort(potions.begin(), potions.end());   // sorting array of potions\n```\n\nNow, it is given in the question that we have to find the number of elements in potions that multiply with spell[i] to give value >= success.\n\nIn simple words: \n$$spells[i] * potions[j]  >=  success$$\n\nTaking spells[i] on R.H.S. we get:\n$$potions[j] >= success / spells[i]$$\n\nSo minimum possible value of potion for spells[i] is `success / spells[i]`. Now, it is clear that we have to find **$$lower bound$$** in our already sorted array of potions. And we know,  all the elements after this lower bound in the potions array will be greater (as the array is sorted in increasing order), so we will get the answer by doing m - lower bound.\n```\nans[i] = m - lower_bound_ind;\n```\nPlease check the code below.\n\n\n\n# Complexity\n- Time complexity: O(n logm)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Please Upvote if it was helpfull.!\uD83D\uDE03\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        int n = spells.size(), m = potions.size();\n        sort(potions.begin(), potions.end());\n        vector<int> ans(n);\n        for (int i{}; i<n; ++i){\n            long long potion = ceil((double)success/spells[i]);\n            int lower_bound_ind = lower_bound(potions.begin(), potions.end(), potion) - potions.begin();\n            ans[i] = m-lower_bound_ind;\n        }\n        return ans;\n    }\n};\n```
['Array', 'Math', 'Binary Search', 'Sorting', 'C++']