✔️✔️Easy Solutions in Java ✔️✔️, Python ✔️, and C++ ✔️🧐Look at once 💻 with Exaplanation
Intuition\n Describe your first thoughts on how to solve this problem. \nFor each spell, we need to find the number of potions that can form a successful pair w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor each spell, we need to find the number of potions that can form a successful pair with it. A pair is successful if the product of their strengths is at least the given success value. To find the number of successful pairs for each spell, we can iterate through the potions array and check if the product of the spell strength and the potion strength is greater than or equal to the success value. If it is, we can increment a counter for that spell. We can then return the counters as an array.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. We start by initializing the output array `pairs` with all zeros, and sorting the `potions` array in ascending order.\n \n2. For each `spell` in `spells`, we perform a binary search on the `potions` array to find the number of `potions` that form a successful pair with the current `spell`. We maintain two pointers `left` and `right` that initially point to the first and last indices\nof the `potions` array, respectively.\n\n3. We repeat the binary search until the `left` and `right` pointers meet or cross each other. In each iteration, we compute the product of the current `spell` and the middle `potion` using long integer multiplication to avoid integer overflow. If the product is greater than or equal to the `success` threshold, we move the `right` pointer to the left of the middle index. Otherwise, we move the `left` pointer to the right of the middle index.\n\n4. Once the binary search is complete, we set the corresponding element of `pairs` to the number of `potions` that come after the `left` pointer in the sorted `potions` array, which are guaranteed to form a successful pair with the current `spell`.\n\n5. Finally, we return the `pairs` array as the result.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this solution is $$O(n log m)$$, where n is the length of `spells` and m is the length of `potions`, due to the binary search. The space complexity is O(1).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is $$O(1)$$, since we only use a constant amount of extra memory to store the `pairs` array and the binary search pointers.\n\n\n![image.png](https://assets.leetcode.com/users/images/b427e686-2e5d-469a-8e7a-db5140022a6b_1677715904.0948765.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n```\n\n# Code\n``` Java []\nclass Solution {\n    public int[] successfulPairs(int[] spells, int[] potions, long success) {\n        int n = spells.length;\n        int m = potions.length;\n        int[] pairs = new int[n];\n        Arrays.sort(potions);\n        for (int i = 0; i < n; i++) {\n            int spell = spells[i];\n            int left = 0;\n            int right = m - 1;\n            while (left <= right) {\n                int mid = left + (right - left) / 2;\n                long product = (long) spell * potions[mid];\n                if (product >= success) {\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            pairs[i] = m - left;\n        }\n        return pairs;\n    }\n}\n\n```\n``` Python []\nclass Solution(object):\n    def successfulPairs(self, spells, potions, success):\n        n = len(spells)\n        m = len(potions)\n        pairs = [0] * n\n        potions.sort()\n        for i in range(n):\n            spell = spells[i]\n            left = 0\n            right = m - 1\n            while left <= right:\n                mid = left + (right - left) // 2\n                product = spell * potions[mid]\n                if product >= success:\n                    right = mid - 1\n                else:\n                    left = mid + 1\n            pairs[i] = m - left\n        return pairs\n\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        int n = spells.size();\n        int m = potions.size();\n        vector<int> pairs(n, 0);\n        sort(potions.begin(), potions.end());\n        for (int i = 0; i < n; i++) {\n            int spell = spells[i];\n            int left = 0;\n            int right = m - 1;\n            while (left <= right) {\n                int mid = left + (right - left) / 2;\n                long long product = (long long)spell * (long long)potions[mid];\n                if (product >= success) {\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            pairs[i] = m - left;\n        }\n        return pairs;\n    }\n};\n\n```\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```
['Array', 'Binary Search', 'Python', 'C++', 'Java']