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

本文介绍: 【代码】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^{th}

$i^{t h}$ spell and potions[j] represents the strength of the

j^{th}

$j^{t h}$ 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}

$i^{t h}$ spell.

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
–

0

t

h

0^{th}

$0^{t h}$ spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
–

1

s

t

1^{st}

$1^{s t}$ spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
–

2

n

d

2^{nd}

$2^{n d}$ 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:
–

0

t

h

0^{th}

$0^{t h}$ spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
–

1

s

t

1^{st}

$1^{s t}$ spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
–

2

n

d

2^{nd}

$2^{n d}$ 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
$10^5 1<=n,m<=105$
$10^5 1<=spells[i],potions[i]<=105$
$10^{10} 1<=success<=1010$

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

Solution:

Ideas：

Sort the Potions Array: First, sort the potions array in non-decreasing order. This step is crucial for the binary search to work.
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.
Allocate Memory for the Result Array: Allocate memory for the result array pairs which will store the count of successful pairs for each spell.
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.
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;
}