# 2300. Successful Pairs of Spells and Potions
###### tags: `Python`,`Leetcode`,`Binary Search`
https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/
## MyCode!

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        m = len(spells)
        n = len(potions)
        output =[0]* m
        potions = sorted(potions)
        for i in range(m):
            spell = spells[i]
            left = 0
            right = n -1 
            while left <= right :
                mid = (left + right) //2
                product = spell * potions[mid]
                if product < success:
                    left = mid + 1
                elif product >= success :
                    right = mid -1
            output[i] = n - left
        return output

## 解題思路 ＆ 步驟
* 我原本寫兩個迴圈，遍歷 spells 跟 potions 內的料，讓他們相乘。但因為有些測資太長，這樣跑會 TLE

# TLE 的 Code
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        output =[]
        for i in range(len(spells)):
            success_times = 0
            for j in range(len(potions)):
                product = spells[i] * potions[j]
                if product >= success:
                    success_times += 1
                else:
                    continue
            output.append(success_times)
        return output
                    

* 所以依照題目所給的 Hint ，可以利用 Binary Search（BS）
* 但 Output 的順序其實跟著 spells 所以可以利用 BS 的可能只有 potions
### Step 1 : 求出 spells、potions 的長度，以利迴圈進行。且把 potions 由小到大排好
* potions 由小到大排好是為了 BS 進行順利

### Step 2 : 創造一個跟 spells 一樣長的 output List
* List 的料 = 0 ，這樣後面如果求出比 success 大的次數可以直接更改 List 的值

### Step 3 : 寫一個 for 迴圈遍歷 spells 裡面所有的數

* spells[i]* potions[mid] = product
* potions 的 index **最小 = left** ，****最大 = right**** ，**中位 mid = (left + right)//2**
1. mid 當最大、最小改變時也會改變，所以要寫在 while 迴圈中一直更新
2. 因為 potions 已經有由小到大排好，如果 product < success 代表現在的 potions[mid] 太小，最小 index 更新為 mid + 1
3. 呈上，如果 product >= success 代表現在的 potions[mid] 太大或剛好，最大 index 更新為 mid-1
4. 當 left > right ，while 迴圈停止， left 會停在剛好 product >= success 處
* 只要算出 left 到原 potions 尾巴有幾個料，就會知道有幾個料跟 spells[i] 相乘會大於 success。再把 output[i] 直接改成這個料數