Successful Spell-Potion Pairs

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;
}

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