Sponsored
Sponsored
This approach involves iterating over each spell and checking the product with every potion to see if it exceeds the 'success' threshold. Though simple to understand and implement, this approach is inefficient for large input sizes due to its O(n * m) time complexity.
Time Complexity: O(n * m) where n is the number of spells and m is the number of potions.
Space Complexity: O(1) aside from the output list which requires O(n).
1def successfulPairs(spells, potions, success):
2 n = len(spells)
3 pairs = [0] * n
4 for i in range(n):
5 count = 0
6 for potion in potions:
7 if spells[i] * potion >= success:
8 count += 1
9 pairs[i] = count
10 return pairsThe function successfulPairs takes three parameters: spells, potions, and success. It iterates over each spell and computes the number of potions that can combine with it to meet the success criterion.
This approach leverages sorting and binary search for optimization. By sorting the potions array, for each spell, we can binary search to find the least potion that meets the success criterion, allowing us to efficiently count the valid potions.
Time Complexity: O(m log m + n log m) due to sorting and binary searches.
Space Complexity: O(1) aside from space for the result list.
1import java.util.Arrays;
2
Java's implementation uses manual binary search to find the lower bound for the required potion strength, allowing it to efficiently determine the number of successful pairs for each spell.