Loading

LeetCode problem#2300

Successful Pairs of Spells and Potions

Solved in 2 languagesJavaRuby

Solve it on LeetCode(opens in a new tab)

Solution

29 lines
1class Solution {
2    public int[] successfulPairs(int[] spells, int[] potions, long success) {
3        int[] pairs = new int[spells.length];
4
5        Arrays.sort(potions);
6
7        for (int i = 0; i < spells.length; i++) {
8            int count = potions.length;
9
10            int left = 0;
11            int right = potions.length - 1;
12
13            while (left <= right) {
14                int mid = left + (right - left) / 2;
15
16                if ((long)potions[mid] * spells[i] < success) {
17                    left = mid + 1;
18                }
19                else {
20                    right = mid - 1;
21                }
22            }
23
24            pairs[i] = count - left;
25        }
26
27        return pairs;
28    }
29}
1# @param {Integer[]} spells
2# @param {Integer[]} potions
3# @param {Integer} success
4# @return {Integer[]}
5def successful_pairs(spells, potions, success)
6  pairs = Array.new spells.length
7
8  potions.sort!
9
10  spells.each_with_index do |spell, index|
11      count = potions.length
12
13      # binary search
14      left = 0
15      right = potions.length - 1
16      while left <= right
17          mid = left + (right - left) / 2
18          if potions[mid] * spell < success
19              left = mid + 1
20          else
21              right = mid - 1
22          end
23      end
24
25      pairs[index] = count - left
26  end
27
28  pairs
29end

Want a walkthrough of this Java solution?

Get a step-by-step explanation of the idea behind the code.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.