369. Potion Pairings
An apprentice has a row of spells and a shelf of potions. Spell i has strength spells[i] and potion j has strength potions[j]. A spell and a potion form a successful pairing if the product of their strengths is at least success.
Return an array pairs of the same length as spells, where pairs[i] is the number of potions that form a successful pairing with spell i. Checking every spell against every potion is O(n * m), which is too slow for the sizes below, so sort the potions and find the first successful potion with a binary search. Use 64-bit arithmetic for the products.
Example 1
- Input:
- spells = [5,1,3], potions = [1,2,3,4,5], success = 7
- Output:
- [4,0,3]
- Explanation:
Spell 5 works with potions 2 to 5 (4 of them), spell 1 with none, and spell 3 with potions 3, 4 and 5.
Example 2
- Input:
- spells = [2], potions = [1,1], success = 5
- Output:
- [0]
- Explanation:
Neither potion reaches a product of 5 with the spell, so the only count is 0.
Constraints
1 ≤ spells.length, potions.length ≤ 105
1 ≤ spells[i], potions[j] ≤ 105
1 ≤ success ≤ 1010
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O((n + m) log m)
- Space
- O(1) extra, plus the output