✅ Java | Easy Solution with Detailed Explaination and Similar problems 📝 | Binary Search
Intuition\nQuestion reduces to finding no of potions for each spell which have \nproduct greater than success where product is (each spell * potions[i])\n\nNow 
# Intuition\nQuestion reduces to finding no of potions for each spell which have \n***product greater than success*** where product is (each spell * potions[i])\n\nNow decision is whether to keep the potions array sorted or not.\n\n- ***NON-SORTED*** Another is to traverse entire array of potions and count no of products(spell * potions[i]) greater than success. But this will take more time as for each spell we will need to traverse entire potions array.\n\n- ***SORTED*** Immediate thought to reduce time complexity of above case is to keep potions array sorted, then question reduces to finding the first occurrence of the product( each spell * potions[i]) which is greater than success, so we go with ***Binary search***\n\n---\n\n\n# Approach\n1) Sort potions array.\n2) For every spell we will find min Index where the product( spell * potion[i]) is greater than success\n3) Once we find such an index via binary search anser for that spell is \npotions.length - minIndex\n4) It is ***important*** how we choose left and right pointers of binary search\n5) I intialised with left = 0, *right = potion.length and not potion.length-1*, since we can have a case where we donot find any minIndex in that case the minIndex will be potion.length and hence result[i] of such spell[i] = potion.length -minIndex = 0\n\n**Similar question[ LC 35 Search and Insert](https://leetcode.com/problems/search-insert-position/) to make you understand point 5 better and how to choose boundaries wisely depending on the question type.**\n\n***Generic binary search [understanding](https://leetcode.com/problems/binary-search/solutions/3364223/java-easy-solution-explained-why-leftright-left2-instead-of-leftright2/)***\n\n\n---\n- Time Complexity\nO(nlogm): where m is the length of potions array and n of spells array\n\n***NOTE***: Reason why 1l is done in ***long product = (1l * spell) * potions[mid];*** because (spell * potions[i]) both being integer will overflow and will result in wrong product value. \nI wasted a lot of time in this.\n\n---\n\nHope it is easy to understand.\nLet me know if there is something unclear and i can fix it.\n\nOtherwise, please upvote if you like the solution, it would be encouraging\n\n![LCUpvote.png](https://assets.leetcode.com/users/images/0cb8949f-630b-4e16-b2c8-2f4e7d2007fb_1680404247.5368462.png)\n\n\n# Code\n```\nclass Solution {\n    public int[] successfulPairs(int[] spells, int[] potions, long success) {\n        int [] result = new int[spells.length];\n        int potionsLength = potions.length;\n        Arrays.sort(potions);\n\n        for(int i=0; i<spells.length; i++){\n            int minIndex = binarySearch(potions, success, spells[i]);\n            result[i] = potionsLength - minIndex;\n        }\n        return result;\n    }\n\n    private int binarySearch(int [] potions, long success, int spell){\n        int left= 0;\n        int right= potions.length;\n        \n        while(left<right){\n            int mid = left + (right-left)/2;\n            long product = (1l * spell) * potions[mid];\n            if(product<success){\n                left=mid+1;\n            }else{\n                right=mid;\n            }\n        }\n\n        return left;\n    }\n}\n\n```
['Binary Search', 'Java']