I’m currently practicing coding problems and found this problem called "Successful Pairs of Spells and Potions", the probelm describtion is as follows;
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:
Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.
Example 2:
Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful.
Thus, [2,0,2] is returned.
I know that this problem could be solved using binary search, but my attempt was an iterative attempt which counts the total of each successful element in each array and inserts them into another array. but for some reason my returned array is all zero’s ([0,0,0]). here is my attempt. I would appreciate any help on finding the bug in my solution, just trying to learn, thanks.
def successfulPairs(self, spells, potions, success):
arr = []
total = 0
first = 0
second = 0
while first < len(spells):
res = spells[first] * potions[second]
for i in range(len(potions)):
if res >= success:
total += 1
second += 1
first += 1
arr.append(total)
total = 0
return arr>Solution :
Your for loop keeps testing the same value of res each time through the loop. Incrementing second doesn’t change the value of res.
You don’t need to use pointers (indexes), just iterate through the list elements. You can use the sum() function to calculate the total, and a generator expression to iterate through the list of potions and do the multiplication.
def successfulPairs(self, spells, potions, success):
arr = []
for spell in spells:
total = sum(spell * potion >= success for potion in potions)
arr.append(total)
return arr