Day 92 || Binary Search || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n \nNOTE 2 - 
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n \n**NOTE 2 - I WILL HIGHLY RECOMMEND YOU GUYS BEFORE SOLVING THIS PROBLEM PLEASE SOLVE BINARY SEARCH PROBLEM.**\n\n**704. Binary Search Problem -** https://leetcode.com/problems/binary-search/\n**704. Binary Search Solution -** https://leetcode.com/problems/binary-search/solutions/3364016/day-91-binary-search-o-logn-time-easiest-beginner-friendly-sol/\n\n# Intuition of this Problem :\n*The problem is asking to find the number of successful pairings between the spells and potions arrays such that the product of their strengths is at least a given integer "success".*\n\n***To solve this problem, we can iterate through each spell and for each spell, we can find the index of the first potion whose strength is at least "success". This can be done using binary search since the potions array is sorted. Once we have the index, the number of successful pairings can be calculated by subtracting the index from the total number of potions. We can repeat this process for each spell and store the number of successful pairings in an array.***\n\n*Finally, we return the array containing the number of successful pairings for each spell.*\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem :\n1. Define a function binarySearch which takes the input integer spell, a vector of integers potions, and a long integer success and returns an integer value.\n2. Initialize the integer startIndex to 0, lastIndex to potions.size() - 1, and ansIndex to -1.\n3. Run a while loop until startIndex is less than or equal to lastIndex.\n4. Within the loop, calculate the midIndex using (startIndex + (lastIndex - startIndex) / 2) to avoid integer overflow.\n5. If the product of spell and the midIndex element of potions is greater than or equal to success, then set ansIndex to midIndex and update lastIndex to midIndex - 1.\n6. Else, update startIndex to midIndex + 1.\n7. Return ansIndex.\n8. Initialize an integer m to the size of the potions vector and create an empty vector ans.\n9. Sort the potions vector in ascending order using sort.\n10. Iterate through each element spell in the spells vector.\n11. Initialize an integer countPair to 0.\n12. Call the binarySearch function with spell, potions, and success as arguments and store the result in the index variable.\n13. If index is equal to -1, then add 0 to countPair, else add m - index to countPair.\n14. Append countPair to ans.\n15. Return ans.\n<!-- Describe your approach to solving the problem. -->\n\n# Code :\n```C++ []\n//1st Approach\n\nclass Solution {\npublic:\n    int binarySearch(int spell, vector<int>& potions, long long success) {\n        int startIndex = 0; \n        int lastIndex = potions.size() - 1;\n        int ansIndex = -1;\n        while(startIndex <= lastIndex){\n            //helps to prevent from out of bound\n            int midIndex = (startIndex + (lastIndex - startIndex) / 2);\n            if ((long long) spell * potions[midIndex] >= success){\n                ansIndex = midIndex;\n                lastIndex = midIndex - 1;\n            }\n            else{\n                startIndex = midIndex + 1;\n            }\n        }\n        return ansIndex;   \n    }\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        sort(potions.begin(), potions.end());\n        int m = potions.size();\n        vector<int> ans;\n        for (int spell : spells) {\n            int countPair = 0;\n            int index = binarySearch(spell, potions, success);\n            if (index == -1) \n                countPair += 0;\n            else\n                countPair += (m - index);\n            ans.push_back(countPair);\n        }\n        return ans;\n    }\n};\n```\n```C++ []\n//2nd Approach\n\nclass Solution {\npublic:\n    int binarySearch(int spell, vector<int>& potions, long long success) {\n        int startIndex = 0; \n        int lastIndex = potions.size() - 1;\n        while(startIndex <= lastIndex){\n            //helps to prevent from out of bound\n            int midIndex = (startIndex + (lastIndex - startIndex) / 2);\n            if ((long long) spell * potions[midIndex] >= success){\n                lastIndex = midIndex - 1;\n            }\n            else{\n                startIndex = midIndex + 1;\n            }\n        }\n        return lastIndex + 1;   \n    }\n    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {\n        sort(potions.begin(), potions.end());\n        int m = potions.size();\n        vector<int> ans;\n        for (int spell : spells) {\n            int index = binarySearch(spell, potions, success);\n            ans.push_back(m - index);\n        }\n        return ans;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int binarySearch(int spell, int[] potions, long success) {\n        int startIndex = 0; \n        int lastIndex = potions.length - 1;\n        int ansIndex = -1;\n        while(startIndex <= lastIndex){\n            int midIndex = (startIndex + (lastIndex - startIndex) / 2);\n            if ((long) spell * potions[midIndex] >= success){\n                ansIndex = midIndex;\n                lastIndex = midIndex - 1;\n            }\n            else{\n                startIndex = midIndex + 1;\n            }\n        }\n        return ansIndex;   \n    }\n    public int[] successfulPairs(int[] spells, int[] potions, long success) {\n        Arrays.sort(potions);\n        int m = potions.length;\n        int[] ans = new int[spells.length];\n        for (int i = 0; i < spells.length; i++) {\n            int countPair = 0;\n            int index = binarySearch(spells[i], potions, success);\n            if (index == -1) \n                countPair += 0;\n            else\n                countPair += (m - index);\n            ans[i] = countPair;\n        }\n        return ans;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def binarySearch(self, spell: int, potions: List[int], success: int) -> int:\n        startIndex = 0\n        lastIndex = len(potions) - 1\n        ansIndex = -1\n        while startIndex <= lastIndex:\n            midIndex = (startIndex + (lastIndex - startIndex) // 2)\n            if spell * potions[midIndex] >= success:\n                ansIndex = midIndex\n                lastIndex = midIndex - 1\n            else:\n                startIndex = midIndex + 1\n        return ansIndex\n    \n    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n        potions.sort()\n        m = len(potions)\n        ans = []\n        for spell in spells:\n            countPair = 0\n            index = self.binarySearch(spell, potions, success)\n            if index == -1:\n                countPair += 0\n            else:\n                countPair += (m - index)\n            ans.append(countPair)\n        return ans\n\n```\n\n# Time Complexity and Space Complexity:\n- **Time Complexity :** **O((n + m) log m)**, where n is the length of the spells vector and m is the length of the potions vector.\n\n*The sort function takes O(m log m) time where \'m\' is the size of the potions vector.\nFor each spell, the binarySearch function is called which takes O(log m) time.\nTherefore, the time complexity of the entire solution is O(n log m + m log m), where \'n\' is the size of the spells vector.*\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space Complexity :** **O(m + n)**, since we need to store the result in the ans vector.\n\n*The space complexity of the solution is O(m) to store the sorted potions vector, and O(n) to store the output vector of size \'n\'.\nTherefore, the total space complexity of the solution is O(m + n).*\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Array', 'Binary Search', 'C++', 'Java', 'Python3']