2300. Successful Pairs of Spells and Potions

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

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful. 
Thus, [2,0,2] is returned.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

Solution:

Spell: 咒语

Potion: 药水

对于正整数, \(xy \ge success\) 等于\(y \geq \left \lceil \frac{success}{x} \right \rceil\).

为了方便二分, 可以利用如下恒等式:

$ \left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b -1}{b} \right \rfloor = \left \lfloor \frac{a - 1}{b} \right \rfloor + 1$

证明见上取整下去整转换公式的证明.

根据上式, 我们有 $$ y \ge \left \lceil \frac{success}{x} \right \rceil = \left \lfloor \frac{success -1}{x} \right \rfloor + 1 $$ 这等价于 $$ y > \left \lfloor \frac{success - 1}{x} \right \rfloor $$ 对 potions 排序后，就可以二分查找了：设 x=spells[i]，j 是最小的满足\(potions[j]> \left \lfloor \frac{success - 1}{x} \right \rfloor\) 的下标，由于数组已经排序，那么下标大于 \(j\) 的也同样满足该式，这一共有 \(m−j\) 个，其中 \(m\) 是 \(potions\) 的长度。

为什么不等式一定要这样变形？好处是每次二分只需要做一次除法，避免多次在二分循环内做乘法，效率更高。另外的好处是部分语言可以直接调用库函数二分。

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = potions.length;
        int m = spells.length;

        int[] result = new int[m];

        Arrays.sort(potions);

        for (int i = 0; i < m; i++){
            // 使用long 避免除法或乘法溢出
            long target = (success + spells[i] -1)/spells[i];
            // 等价于 Math.ceil(success / spells[i])
            int first = binarySearch(potions, target);
            if (first == n || potions[first] < target){
                result[i] = 0;
            }else{
                result[i] = n - first;  
            }


        }

        return result;
    }

    private int binarySearch(int[] nums, long target){
        // return >= 0
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if (nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        return left;
    }
}