aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--patching_array.c54
-rw-r--r--patching_array.py43
2 files changed, 97 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
+}
diff --git a/patching_array.py b/patching_array.py
new file mode 100644
index 0000000..de7d5a2
--- /dev/null
+++ b/patching_array.py
@@ -0,0 +1,43 @@
+# 330. Patching Array
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def merge(self, intervals):
+ intervals.sort(key=lambda x: x[0])
+ merged = []
+ for i in intervals:
+ if not merged or merged[-1][1] < i[0] - 1:
+ merged.append(i)
+ else:
+ merged[-1][1] = max(merged[-1][1], i[1])
+ return merged
+
+ def minPatches(self, nums, n):
+ """
+ :type nums: List[int]
+ :type n: int
+ :rtype: int
+ """
+ ints, patches = [[0, 0]], 0
+ for i in nums:
+ ints = self.merge(ints + [[j + i, k + i] for j, k in ints])
+ while ints[0][1] < n:
+ ints = self.merge(
+ ints + [[i + ints[0][1] + 1, j + ints[0][1] + 1] for i, j in ints]
+ )
+ patches += 1
+ return patches
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minPatches(nums=[1, 3], n=6))
+ print(obj.minPatches(nums=[1, 5, 10], n=20))
+ print(obj.minPatches(nums=[1, 2, 2], n=5))