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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end());
int n = spells.size();
int m = potions.size();
vector<int> results(n, 0);
for (int i = 0; i < n; ++i) {
long long minPotionStrength = (success + spells[i] - 1) / spells[i];
int index = lower_bound(potions.begin(), potions.end(), minPotionStrength) - potions.begin();
results[i] = m - index;
}
return results;
}This solution employs C++'s lower_bound to achieve the same binary search functionality, which returns an iterator to the first element not considered less than the given value, giving efficient count of valid potions.