[Solved] Successful Pairs of Spells and Potions LeetCode Contest Problem

Successful Pairs of Spells and Potions: 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.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

Solution:

Explanation

For each spell,
it needs ceil integer of need = success * 1.0 / spell.

Binary search the index of first potion >= need in the sorted potions.
The number of potions that are successful are potions.length - index

Accumulate the result res and finally, return it.

Complexity

Time O(mlogm + nlogm)
Space O(n)

    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> res;
        for (int a: spells) {
            long need = (success + a - 1) / a;
            auto it = lower_bound(potions.begin(), potions.end(), need);
            res.push_back(potions.end() - it);
        }
        return res;
    }

    def successfulPairs(self, spells, potions, success):
        potions.sort()
        return [len(potions) - bisect_left(potions, (success + a - 1) // a) for a in spells]

	public int[] successfulPairs(int[] spells, int[] potions, long success) {
		Arrays.sort(potions);
		TreeMap<Long, Integer> map = new TreeMap<>();
        map.put(Long.MAX_VALUE, potions.length);
		for (int i = potions.length - 1; i >= 0; i--) {
			map.put((long) potions[i], i);
		}
		for (int i = 0; i < spells.length; i++) {
            long need = (success + spells[i] - 1) / spells[i];
			spells[i] = potions.length - map.ceilingEntry(need).getValue();
		}
		return spells;
	}

class Solution {
    typedef long long ll;
    typedef long double ld;
    typedef vector<ll> vi;
    typedef pair<ll, ll> pi;
#define endl '\n'
    static const ll mod = 1e9;
public:
    vector<int> successfulPairs(vector<int>& s, vector<int>& p, long long suc) {
        ll n = s.size(), m = p.size();
        vector<int> res(n, 0);
        sort(p.begin(), p.end());
        for (ll i = 0;i < n;i++) {
            ll l = 0,
                r = m - 1,
                ind = -1;
            while (l <= r) {
                ll m = l + ((r - l) >> 1),
                    prod = ll(s[i]) * ll(p[m]);
                if (prod >= suc) {
                    ind = m;
                    r = m - 1;
                    continue;
                }
                l = m + 1;
            }
            if (ind > -1)
                res[i] = m - ind;
        }
        return res;
    }
};

Happy Learning – If you require any further information, feel free to contact me.