Successful Pairs of Spells and Potions
Successful Pairs of Spells and Potions: for each spell, count how many potions produce a product of at least success when multiplied with it.
- n == spells.length, m == potions.length
- 1 <= n, m <= 10⁵
- 1 <= spells[i], potions[i] <= 10⁵
- 1 <= success <= 10¹⁰
Intuition
For a fixed spell, spell * potion >= success rearranges to potion >= success / spell — a single threshold. Sort the potions once, then every spell becomes a binary search for the first potion at or above its threshold; everything from there to the end succeeds.
When a per-item condition can be rearranged into 'value ≥ threshold', a sorted array plus binary search answers each query in logarithmic time. The tell is a pairwise condition where one side is constant within the query. Same shape as Two Sum II, Search Insert Position, and any 'count elements at least X' question.
Approach
Before reading on: fix one spell and rearrange the success condition so the potion sits alone on one side. What does that turn each query into, and what must the potions array look like first? Aim for O((n + m) log m).
Turn the product condition into a threshold
The condition spell * potion >= success involves two moving parts, which is what makes the brute force feel necessary. But the spell is fixed inside each query, so divide through: a potion succeeds exactly when potion >= success / spell. Now the question per spell is 'how many potions are at least this value', which is a rank query — and rank queries on a sorted array are binary search.
Sort once, search many times
Sorting the potions costs O(m log m) and is done a single time for all spells. For each spell, binary search for the leftmost index whose potion meets the threshold; the count is m - index, since the array is sorted and everything to the right is at least as large. With n spells this gives O(n log m) for the queries, so the total is O((n + m) log m) — comfortably inside the 10⁵ constraints where the O(n·m) brute force would be 10¹⁰ operations.
Avoiding floating-point error
success / spell is a real number and floating-point rounding can misclassify a potion sitting exactly on the boundary — a genuine wrong answer, not a style issue. Two safe options: use integer ceiling division, threshold = (success + spell - 1) // spell, so the comparison stays in integers; or binary search directly on the product potion * spell >= success. Both keep everything exact; with values up to 10⁵ the product fits in 64 bits, so use long in Java and C++.
Solution & live demo
Common pitfalls
Floating-point division for the threshold
threshold = success / spell
threshold = -(-success // spell) # integer ceiling
Values on the exact boundary can round the wrong way, so a potion that should succeed is excluded. Integer ceiling division keeps the comparison exact.
Not sorting the potions
index = bisect_left(potions, threshold) # unsorted
potions.sort() index = bisect_left(potions, threshold)
Binary search assumes order. On an unsorted array it returns an arbitrary position and the counts are silently wrong rather than crashing.
Overflow in the product comparison
int product = spell * potion;
long product = (long) spell * potion;
10⁵ × 10⁵ = 10¹⁰ exceeds a 32-bit int in C++ and Java, wrapping to a negative value and failing the comparison. Python integers are arbitrary precision so this bites only in the ported versions.
Edge cases
The binary search returns m and the count is 0.
The search returns index 0 and the count is m.
Integer ceiling division keeps it inclusive, so that potion counts.
10⁵ × 10⁵ = 10¹⁰ overflows a 32-bit int; use 64-bit arithmetic in C++ and Java.
The search covers a one-element array and returns 0 or 1 correctly.