aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-10-07 19:36:44 -0600
committerJack Sangdahl <[email protected]>2025-10-07 19:36:44 -0600
commitf3e447ec79036fda15e973ff7d0ea81cbebb4532 (patch)
tree4670b1aa23699ac2823506bf57d25c606d622761
parentb7c6bb41d702904d2d221919de01aed1e0e9f13c (diff)
downloadleetcode-f3e447ec79036fda15e973ff7d0ea81cbebb4532.tar.gz
leetcode-f3e447ec79036fda15e973ff7d0ea81cbebb4532.zip
2300. successful pairs of spells and potions
-rw-r--r--pairs_spells_potions.c59
-rw-r--r--pairs_spells_potions.py39
2 files changed, 67 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);
}
diff --git a/pairs_spells_potions.py b/pairs_spells_potions.py
new file mode 100644
index 0000000..d9cebea
--- /dev/null
+++ b/pairs_spells_potions.py
@@ -0,0 +1,39 @@
+# 2300. Successful Pairs of Spells and Potions
+from bisect import bisect_left
+from math import ceil
+
+"""
+given two positive integer arrays 'spells' and 'potions', of length n and m
+respectively where 'spells[i]' represents the strength of the i'th spell and
+'potions[j] represents the strength of the j'th potion. 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
+lengthn where 'pairs[i]' is the number of potions that will form a successful
+pair with the i'th spell.
+"""
+
+
+class Solution(object):
+ def successfulPairs(self, spells, potions, success):
+ """
+ :type spells: List[int]
+ :type potions: List[int]
+ :type success: int
+ :rtype: List[int]
+ """
+ potions.sort()
+ n, ans = len(potions), []
+ for i in spells:
+ req = ceil(success / i)
+ if req > potions[-1]:
+ ans.append(0)
+ continue
+ idx = bisect_left(potions, req)
+ ans.append(n - idx)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.successfulPairs(spells=[5, 1, 3], potions=[1, 2, 3, 4, 5], success=7))
+ print(obj.successfulPairs(spells=[3, 1, 2], potions=[8, 5, 8], success=16))