SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The task is to determine how many potions each spell can successfully pair with to meet or exceed a given success threshold. Given two lists, spells and potions, and a success threshold, for each spell, we need to count the number of potions that can be paired with it such that the product of the spell and potion is at least the success threshold.

Intuition

To solve this problem efficiently, we need to determine for each spell how many potions meet the requirement to achieve the success threshold. A brute force approach could involve checking each spell against every potion, which would be too slow. Instead, we can leverage sorting and binary search to achieve an optimal solution.

Approach

1. Calculate Required Values: For each potion, compute the minimum value required from a spell to achieve the success threshold when paired with that potion. This is done using the formula ceil(success / potion) for each potion.

2. Sort Values: Sort these computed values in ascending order.

3. Binary Search: For each spell, use binary search to determine how many of the sorted values are less than or equal to the spell value. This will give the count of valid potions for that spell.

4. Store Results: Collect the results for each spell and return them.

Complexity

Time Complexity:

(O(m \log m + n \log m)), where (m) is the number of potions and (n) is the number of spells. Sorting the potions takes (O(m \log m)), and for each spell, performing a binary search on the sorted list takes (O(\log m)), resulting in (O(n \log m)) for all spells.

Space Complexity:

(O(m + n)) due to the space needed for storing the sorted values and the result array.

Code

C++

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<long long> arr; // Use long long to handle large numbers
        for (int potion : potions) {
            arr.push_back(ceil(success / (double)potion)); // Ensure double division for accurate results
        }
        sort(arr.begin(), arr.end());

        vector<int> res;
        for (int spell : spells) {
            int l = 0, r = arr.size() - 1, M = 0;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (arr[m] <= spell) {
                    l = m + 1;
                    M = l;
                } else {
                    r = m - 1;
                }
            }
            res.push_back(M);
        }

        return res;
    }
};

Python

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        arr = [math.ceil(success / potion) for potion in potions]
        arr.sort()

        res = []
        for spell in spells:
            l, r, M = 0, len(arr) - 1, 0
            while l <= r:
                m = (l + r) // 2
                if arr[m] <= spell:
                    l = m + 1
                    M = l
                else:
                    r = m - 1
            res.append(M)

        return res

Java

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        List<Long> arr = new ArrayList<>();
        for (int potion : potions) {
            arr.add((long) Math.ceil((double) success / potion)); // Use long for large numbers
        }
        Collections.sort(arr);

        int[] res = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            int spell = spells[i];
            int l = 0, r = arr.size() - 1, M = 0;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (arr.get(m) <= spell) {
                    l = m + 1;
                    M = l;
                } else {
                    r = m - 1;
                }
            }
            res[i] = M;
        }

        return res;
    }
}

JavaScript

var successfulPairs = function(spells, potions, success) {
    let arr = [];
    for(let potion of potions) {
        arr.push(Math.ceil(success / potion));
    }
    arr.sort((a,b) => a-b);
    const n = arr.length;
    console.log(arr);

    const res = [];
    for(let spell of spells) {
        let l=0, r=n-1, M=0;
        while(l<=r) {
            let m = Math.floor((l+r)/2);
            if(arr[m] <= spell) {
                l = m+1;
                M = l;
            } else {
                r = m-1;
            }
        }
        res.push(M);
    }  
    return res;
};