LeetCode //C - 2300. Successful Pairs of Spells and Potions

2300. 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 i t h i^{th} ith spell and potions[j] represents the strength of the j t h j^{th} 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 i t h i^{th} ith spell.
 

Example 1:

Example 2:

Constraints:

• n == spells.length
• m == potions.length
• 1 < = n , m < = 1 0 5 1 <= n, m <= 10^5 1<=n,m<=105
• 1 < = s p e l l s [ i ] , p o t i o n s [ i ] < = 1 0 5 1 <= spells[i], potions[i] <= 10^5 1<=spells[i],potions[i]<=105
• 1 < = s u c c e s s < = 1 0 10 1 <= success <= 10^{10} 1<=success<=1010

From: LeetCode
Link: 2300. Successful Pairs of Spells and Potions

---

Solution:

Ideas：

1. Sort the Potions Array: First, sort the potions array in non-decreasing order. This step is crucial for the binary search to work.

2. Binary Search Function: Implement a binary search function that returns the number of potions that, when multiplied by the current spell’s strength, meet or exceed the success threshold.

3. Allocate Memory for the Result Array: Allocate memory for the result array pairs which will store the count of successful pairs for each spell.

4. Iterate Over Spells and Apply Binary Search: For each spell, apply the binary search on the sorted potions array to find how many potions can form a successful pair with it.

5. Return the Result: Update the returnSize to be equal to spellsSize and return the pairs array.

Caode:

// Comparator function for qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// Binary search to find the number of successful pairs
int findSuccessfulPairs(int spell, int* potions, int potionsSize, long long success) {
    int left = 0, right = potionsSize - 1, count = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if ((long long)spell * potions[mid] >= success) {
            count = potionsSize - mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return count;
}

int* successfulPairs(int* spells, int spellsSize, int* potions, int potionsSize, long long success, int* returnSize) {
    // Sort the potions array
    qsort(potions, potionsSize, sizeof(int), compare);
    
    // Allocate memory for the result array
    int* pairs = (int*)malloc(spellsSize * sizeof(int));
    if (!pairs) return NULL; // In case malloc fails
    
    // For each spell, find the number of successful pairs using binary search
    for (int i = 0; i < spellsSize; i++) {
        pairs[i] = findSuccessfulPairs(spells[i], potions, potionsSize, success);
    }
    
    // Set the return size
    *returnSize = spellsSize;
    
    return pairs;
}