Successful Pairs of Spells and Potions

medium binary search sorting

Problem

Given spells, potions, and a success threshold, return for each spell how many potions form a successful pair (product ≥ threshold). Sort potions, then for each spell binary search for the smallest potion ≥ ceil(threshold / spell).

Inputspells = [5,1,3], potions = [1,2,3,4,5], success = 7

Output[4, 0, 3]

For spell 5: need potion ≥ 2 → 4 of them. For 1: need 7 (none). For 3: need 3 → 3 potions.

spells (comma-separated positives)

potions

threshold

from bisect import bisect_left
def successful_pairs(spells, potions, T):
    potions.sort()
    out = []
    for s in spells:
        need = -(-T // s)
        out.append(len(potions) - bisect_left(potions, need))
    return out

function successfulPairs(spells, potions, T) {
  potions.sort((a, b) => a - b);
  return spells.map(s => {
    const need = Math.ceil(T / s);
    let l = 0, r = potions.length;
    while (l < r) { const m = (l + r) >> 1; if (potions[m] < need) l = m + 1; else r = m; }
    return potions.length - l;
  });
}

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long T) {
        Arrays.sort(potions);
        int[] ans = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            long need = (T + spells[i] - 1) / spells[i];
            int l = 0, r = potions.length;
            while (l < r) { int m = (l + r) >>> 1; if (potions[m] < need) l = m + 1; else r = m; }
            ans[i] = potions.length - l;
        }
        return ans;
    }
}

vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long T) {
    sort(potions.begin(), potions.end());
    vector<int> ans(spells.size());
    for (int i = 0; i < (int)spells.size(); i++) {
        long long need = (T + spells[i] - 1) / spells[i];
        int l = 0, r = (int)potions.size();
        while (l < r) { int m = (l + r) / 2; if (potions[m] < need) l = m + 1; else r = m; }
        ans[i] = (int)potions.size() - l;
    }
    return ans;
}

Explanation

For each spell we need to count how many potions are strong enough that spell * potion >= success. Checking every potion for every spell would be slow, so we sort the potions once and then use binary search for each spell.

The key rewrite: spell * potion >= success is the same as potion >= success / spell. We round that threshold up to a whole number, need = ceil(success / spell), so a potion counts only if it is at least need.

Because the potions are sorted, binary search finds the first potion that is >= need. Every potion from that position to the end also qualifies, so the count is simply len(potions) - index.

Example: potions = [1,2,3,4,5], success = 7. For spell = 5, need = ceil(7/5) = 2; the first potion >= 2 is at index 1, leaving 5 - 1 = 4 potions. For spell = 1, need = 7 and none reach it, so 0.

Sorting costs m log m once, and each of the n spells does a fast binary search, which is why this is much faster than checking every pair.

Time: O((n + m) log m) Space: O(1) beyond output