LeetCode75-2300-Successful-Pairs-of-Spells-and-Potions

🧠 Summary of Thoughts

Sort + Binary Search for the first valid threshold

1. For each spell, count how many potions satisfy: spell * potion >= success
2. If a potion works, then all stronger potions will also work. So this actually transfer the quesiton to asking what is the index of threshold (Binary Search)
3. potion >= ceil(success / spell)
   • ceil(a / b) = (a + b - 1) / b

✅ Code（Java）

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] pairs = new int[spells.length];
        int m = potions.length;
        for (int i = 0; i < spells.length; i++) {
            long need = (success + spells[i] - 1) / spells[i];
            int left = 0;
            int right = m - 1;
            int idx = m;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (need <= potions[mid]) {
                    idx = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            pairs[i] = m - idx;
        }
        return pairs;
    }
}