diff options
-rw-r--r-- | patching_array.c | 54 | ||||
-rw-r--r-- | patching_array.py | 43 |
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)) |