diff options
author | Jack Sangdahl <[email protected]> | 2025-10-07 19:36:44 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-07 19:36:44 -0600 |
commit | f3e447ec79036fda15e973ff7d0ea81cbebb4532 (patch) | |
tree | 4670b1aa23699ac2823506bf57d25c606d622761 /pairs_spells_potions.c | |
parent | b7c6bb41d702904d2d221919de01aed1e0e9f13c (diff) | |
download | leetcode-f3e447ec79036fda15e973ff7d0ea81cbebb4532.tar.gz leetcode-f3e447ec79036fda15e973ff7d0ea81cbebb4532.zip |
2300. successful pairs of spells and potions
Diffstat (limited to 'pairs_spells_potions.c')
-rw-r--r-- | pairs_spells_potions.c | 59 |
1 files changed, 28 insertions, 31 deletions
diff --git a/pairs_spells_potions.c b/pairs_spells_potions.c index 6981016..acfbd21 100644 --- a/pairs_spells_potions.c +++ b/pairs_spells_potions.c @@ -1,6 +1,5 @@ // 2300. Successful Pairs of Spells and Potions -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given two positive integer arrays 'spells' and 'potions', of length n and m @@ -14,45 +13,43 @@ int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } -int find_successful(int *potions, int potions_size, double val) { - int left = 0, right = potions_size - 1, mid; - while (left < right) { - mid = (left + right) >> 1; - if ((double)potions[mid] >= val) - right = mid; - else - left = mid + 1; +int lower_bound(int *arr, int arr_size, long long target) { + int low = 0, high = arr_size - 1, res = arr_size; + while (low <= high) { + int mid = low + (high - low) / 2; + if (arr[mid] >= target) { + res = mid; + high = mid - 1; + } else + low = mid + 1; } - if ((double)potions[left] >= val) - return potions_size - left; - else - return 0; + return res; } -int *successfulPairs(int *spells, int spells_size, int *potions, - int potions_size, long long success, int *return_size) { - int i, j; - qsort(potions, potions_size, sizeof(int), cmp); - double *spells_float = malloc(spells_size * sizeof(double)); - for (i = 0; i < spells_size; i++) - spells_float[i] = 1.0 * success / spells[i]; - *return_size = spells_size; - int *ans = malloc(spells_size * sizeof(int)); - for (i = 0; i < spells_size; i++) - ans[i] = find_successful(potions, potions_size, spells_float[i]); - free(spells_float); +int *successfulPairs(int *spells, int spellsSize, int *potions, int potionsSize, + long long success, int *returnSize) { + qsort(potions, potionsSize, sizeof(int), cmp); + int *ans = (int *)malloc(spellsSize * sizeof(int)); + *returnSize = spellsSize; + for (int i = 0; i < spellsSize; i++) { + long long req = (success + spells[i] - 1) / spells[i]; + ans[i] = potionsSize - lower_bound(potions, potionsSize, req); + } return ans; } int main() { int s1[] = {5, 1, 3}, s2[] = {3, 1, 2}; int p1[] = {1, 2, 3, 4, 5}, p2[] = {8, 5, 8}; - int rs1[] = {3}, rs2[] = {3}; - int *ex1 = successfulPairs(s1, 3, p1, 5, 7, rs1); - int *ex2 = successfulPairs(s2, 3, p2, 3, 16, rs2); - for (int i = 0; i < 3; i++) + int rs1, + *ex1 = successfulPairs(s1, ARRAY_SIZE(s1), p1, ARRAY_SIZE(p1), 7, &rs1); + int rs2, + *ex2 = successfulPairs(s2, ARRAY_SIZE(s2), p2, ARRAY_SIZE(p2), 16, &rs2); + for (int i = 0; i < rs1; i++) printf("%d ", ex1[i]); // expect: 4 0 3 printf("\n"); - for (int i = 0; i < 3; i++) + for (int i = 0; i < rs2; i++) printf("%d ", ex2[i]); // expect: 2 0 2 + free(ex1); + free(ex2); } |