Successful Pairs of Spells and Potions

The key idea

Sort potions once. For a fixed spell, the product spell * potion rises as the potion grows, so the potions that succeed form a suffix of the sorted array. Binary-search the first index where spell * potions[i] >= success; every potion from there to the end is a success, so the count is m - that index.

Problem

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the i-th spell and potions[j] represents the strength of the j-th 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 i-th spell.

Constraints

1 <= n, m <= 10^5
1 <= spells[i], potions[i] <= 10^5
1 <= success <= 10^10

Examples

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7 Output: [4,0,3]

Input: spells = [3,1,2], potions = [8,5,8], success = 16 Output: [2,0,2]

Complexity

Time: O((n + m) log m) Space: O(m)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →