You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

&nbsp;
Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.


Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful. 
Thus, [2,0,2] is returned.


&nbsp;
Constraints:


	n == spells.length
	m == potions.length
	1 &lt;= n, m &lt;= 105
	1 &lt;= spells[i], potions[i] &lt;= 105
	1 &lt;= success &lt;= 1010


class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        result = self.function(spells,potions,success)
        return result

    def function(self,arr1,arr2,success):
        n2 = len(arr2)
        arr2.sort() #Sorting Enables Us To Do Binary Search
        ans = []
        for i in arr1:
            val = math.ceil(success/i) #Finding the Value Of Portion With Least Strength So That It Can Be Greater Than Success
            idx = bisect.bisect_left(arr2,val) #Finding The Left Most Index So That The Value Can Be Inserted
            res = n2-idx+1 #Calculating the remaining numbers after finding the suitable index
            ans.append(res-1)
        return ans
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        int[] pairs = new int[n];
        Arrays.sort(potions);
        for (int i = 0; i < n; i++) {
            int spell = spells[i];
            int left = 0;
            int right = m - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                long product = (long) spell * potions[mid];
                if (product >= success) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            pairs[i] = m - left;
        }
        return pairs;
    }
}
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        
        vector<int> res;
        int n(size(potions));
        sort(begin(potions), end(potions));
        
        for (auto& spell : spells) {
            int start(0), end(n);
            while (start < end) {
                int mid = start + (end-start)/2;
                ((long long)spell*potions[mid] >= success) ? end = mid : start = mid+1;
            }
            res.push_back(n-start);
        }
        return res;
    }
};
/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
 var successfulPairs = function(spells, potions, success) {
    let res = [];
    potions.sort((a, b) => b-a);
    let map = new Map();
    
    for(let i=0; i<spells.length; i++){
        if(!map.has(spells[i])){
            let s = success / spells[i];
            let len = search(potions, s);
            res.push(len);
            map.set(spells[i], len);
        }else{
            let len = map.get(spells[i]);
            res.push(len);
        }
    }
    
    return res;
};

function search(potions, target){
    let res = 0;
    let left = 0;
    let right = potions.length-1;
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(potions[mid] < target){
            right = mid - 1;
        }else{
            left = mid + 1;
            res = mid + 1;
        }
    }

    return res;
}
Successful Pairs of Spells and Potions