aboutsummaryrefslogtreecommitdiff
path: root/pairs_spells_potions.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-10-07 19:36:44 -0600
committerJack Sangdahl <[email protected]>2025-10-07 19:36:44 -0600
commitf3e447ec79036fda15e973ff7d0ea81cbebb4532 (patch)
tree4670b1aa23699ac2823506bf57d25c606d622761 /pairs_spells_potions.py
parentb7c6bb41d702904d2d221919de01aed1e0e9f13c (diff)
downloadleetcode-f3e447ec79036fda15e973ff7d0ea81cbebb4532.tar.gz
leetcode-f3e447ec79036fda15e973ff7d0ea81cbebb4532.zip
2300. successful pairs of spells and potions
Diffstat (limited to 'pairs_spells_potions.py')
-rw-r--r--pairs_spells_potions.py39
1 files changed, 39 insertions, 0 deletions
diff --git a/pairs_spells_potions.py b/pairs_spells_potions.py
new file mode 100644
index 0000000..d9cebea
--- /dev/null
+++ b/pairs_spells_potions.py
@@ -0,0 +1,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))