2300: Successful-Pairs-of-Spells-and-Potions
Medium

table of contents

Simply, sort potions from smallest to largest.

sort(potions.begin(), potions.end());

Then, simply iterate through spells, dividing success with newSuccess and binary searching where success / newSuccess should go inside of potions. This allows you to calculate the number of successfulPairs in log(n) time.

for (int& i : spells) {
    long long newSuccess = success / i - (success % i == 0 ? 1 : 0);
    auto it = upper_bound(potions.begin(), potions.end(), newSuccess);
    ans.push_back(potions.end() - it);
}

code

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> ans;

        for (int& i : spells) {
            long long newSuccess = success / i - (success % i == 0 ? 1 : 0);
            auto it = upper_bound(potions.begin(), potions.end(), newSuccess);
            ans.push_back(potions.end() - it);
        }

        return ans;
    }
};

complexity

time taken