aboutsummaryrefslogtreecommitdiff
path: root/pairs_spells_potions.py
blob: d9cebea9ff6d319c8c7b133bc06a9e3b709f0b8b (plain)
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
28
29
30
31
32
33
34
35
36
37
38
39
# 2300. Successful Pairs of Spells and Potions
from bisect import bisect_left
from math import ceil

"""
given two positive integer arrays 'spells' and 'potions', of length n and m
respectively where 'spells[i]' represents the strength of the i'th spell and
'potions[j] represents the strength of the j'th potion. 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
lengthn where 'pairs[i]' is the number of potions that will form a successful
pair with the i'th spell.
"""


class Solution(object):
    def successfulPairs(self, spells, potions, success):
        """
        :type spells: List[int]
        :type potions: List[int]
        :type success: int
        :rtype: List[int]
        """
        potions.sort()
        n, ans = len(potions), []
        for i in spells:
            req = ceil(success / i)
            if req > potions[-1]:
                ans.append(0)
                continue
            idx = bisect_left(potions, req)
            ans.append(n - idx)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.successfulPairs(spells=[5, 1, 3], potions=[1, 2, 3, 4, 5], success=7))
    print(obj.successfulPairs(spells=[3, 1, 2], potions=[8, 5, 8], success=16))