Description

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:

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

Example 2:

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

Constraints:

  • n == spells.length
  • m == potions.length
  • 1 <= n, m <= 10^5
  • 1 <= spells[i], potions[i] <= 10^5
  • 1 <= success <= 10^10

Solution

There are couple of approaches to solve this problem.

1: Brute Force

The brute force approach is to iterate over all the spells and potions and check if the product of their strengths is at least success. If it is, then increment the count of successful pairs for that spell.

 1public int[] successfulPairs(int[] spells, int[] potions, int success) {
 2    int n = spells.length;
 3    int m = potions.length;
 4    int[] pairs = new int[n];
 5    
 6    for (int i = 0; i < n; i++) {
 7        for (int j = 0; j < m; j++) {
 8            if ((long)spells[i] * potions[j] >= success) {
 9                pairs[i]++;
10            }
11        }
12    }
13    
14    return pairs;
15}

In this case, we can sort the potions array and for each spell, we can find the number of potions that will form a successful pair using binary search.

 1class Solution {
 2    public int[] successfulPairs (int[] spells, int[] potions, long success) {
 3        int n = spells.length;
 4        int m = potions.length;
 5        int[] pairs = new int[n];
 6        Arrays.sort(potions);
 7        int maxPotion = potions[m - 1];
 8
 9        for (int i = 0; i < n; i++) {
10            long target = (long) Math.ceil(1.0 * success / spells[i]);
11            if (target > maxPotion) {
12                pairs[i] = 0;
13                continue;
14            }
15
16            int firstIndex = indexForNumberLowerThanTarget(potions, (int) target);
17            pairs[i] = m - firstIndex;
18        }
19        return pairs;
20    }
21
22    private int indexForNumberLowerThanTarget(int[] arr, int target) {
23        int left = 0;
24        int right = arr.length;
25
26        while (left < right) {
27            int mid = left + (right - left) / 2;
28            if (arr[mid] < target) {
29                left = mid + 1;
30            } else {
31                right = mid;
32            }
33        }
34
35        return left < arr.length ? left : -1;
36    }
37}