2300. Successful Pairs of Spells and Potions 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);

        int[] counts = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            counts[i] = getCeilingCount(potions, spells[i], success);
        }
        return counts;
    }

    private int getCeilingCount(int[] potions, long spell, long success) {
        int count = 0;
        int left = 0, right = potions.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (spell * potions[mid] >= success) {
                count = Math.max(count, potions.length - mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return count;
    }
}

Binary Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);

        int[] counts = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            counts[i] = getCeilingCount(potions, spells[i], success);
        }
        return counts;
    }

    private int getCeilingCount(int[] potions, long spell, long success) {
        int left = 0, right = potions.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (spell * potions[mid] >= success) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // now: right, left. 此时 left 指向最后一个满足条件的元素
        return potions.length - left;
    }
}

References

2300. Successful Pairs of Spells and Potions