aboutsummaryrefslogtreecommitdiff
path: root/patching_array.py
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.py
parentbfa816e4d0bcdb3996fb4d0de074dbf71155373d (diff)
downloadleetcode-6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a.tar.gz
leetcode-6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a.zip
330. patching array
Diffstat (limited to 'patching_array.py')
-rw-r--r--patching_array.py43
1 files changed, 43 insertions, 0 deletions
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))