aboutsummaryrefslogtreecommitdiff
path: root/patching_array.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-15 18:41:41 -0600
committerjack <[email protected]>2024-06-15 18:41:41 -0600
commit6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a (patch)
tree8156afe68442510cb7de03e7a07a2b6f68aaee69 /patching_array.c
parentbfa816e4d0bcdb3996fb4d0de074dbf71155373d (diff)
downloadleetcode-6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a.tar.gz
leetcode-6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a.zip
330. patching array
Diffstat (limited to 'patching_array.c')
-rw-r--r--patching_array.c54
1 files changed, 54 insertions, 0 deletions
diff --git a/patching_array.c b/patching_array.c
new file mode 100644
index 0000000..2396a1f
--- /dev/null
+++ b/patching_array.c
@@ -0,0 +1,54 @@
+// 330. Patching Array
+#include "leetcode.h"
+
+/*
+ * given a sorted integer array 'nums' and an integer 'n', add/patch elements to
+ * the array such that any number in the range '[1, n]' inclusive can be formed
+ * by the sum of some elements in the array. return the minimum number of
+ * patches required.
+ */
+
+int leading_bit(int n) {
+ int pos = -1;
+ for (int i = 0; i < 32; i++) {
+ if ((n & 1) == 1)
+ pos = i;
+ n >>= 1;
+ }
+ return pos;
+}
+
+int minPatches(int *nums, int numsSize, int n) {
+ int cnt = 0;
+ long long reachable = 1;
+ if (!numsSize)
+ return leading_bit(n) + 1;
+ if (numsSize == 1)
+ return leading_bit(n);
+ if (nums[0] != 1)
+ cnt++;
+ int i = 1 - cnt;
+ while (i < numsSize && reachable < n) {
+ if (nums[i] <= reachable + 1) {
+ reachable += nums[i];
+ i++;
+ } else {
+ cnt++;
+ reachable += reachable + 1;
+ }
+ if (reachable >= n)
+ return cnt;
+ }
+ while (reachable < n) {
+ reachable += reachable + 1;
+ cnt++;
+ }
+ return cnt;
+}
+
+int main() {
+ int n1[] = {1, 3}, n2[] = {1, 5, 10}, n3[] = {1, 2, 2};
+ printf("%d\n", minPatches(n1, ARRAY_SIZE(n1), 6)); // expect: 1
+ printf("%d\n", minPatches(n2, ARRAY_SIZE(n2), 20)); // expect: 2
+ printf("%d\n", minPatches(n3, ARRAY_SIZE(n3), 5)); // expect: 0
+}