Welcome to Subscribe On Youtube
330. Patching Array
Description
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.
Example 1:
Input: nums = [1,3], n = 6 Output: 1 Explanation: Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch.
Example 2:
Input: nums = [1,5,10], n = 20 Output: 2 Explanation: The two patches can be [2, 4].
Example 3:
Input: nums = [1,2,2], n = 5 Output: 0
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 104numsis sorted in ascending order.1 <= n <= 231 - 1
Solutions
-
class Solution { public int minPatches(int[] nums, int n) { long x = 1; int ans = 0; for (int i = 0; x <= n;) { if (i < nums.length && nums[i] <= x) { x += nums[i++]; } else { ++ans; x <<= 1; } } return ans; } } -
class Solution { public: int minPatches(vector<int>& nums, int n) { long long x = 1; int ans = 0; for (int i = 0; x <= n;) { if (i < nums.size() && nums[i] <= x) { x += nums[i++]; } else { ++ans; x <<= 1; } } return ans; } }; -
class Solution: def minPatches(self, nums: List[int], n: int) -> int: x = 1 ans = i = 0 while x <= n: if i < len(nums) and nums[i] <= x: x += nums[i] i += 1 else: ans += 1 x <<= 1 return ans -
func minPatches(nums []int, n int) (ans int) { x := 1 for i := 0; x <= n; { if i < len(nums) && nums[i] <= x { x += nums[i] i++ } else { ans++ x <<= 1 } } return } -
function minPatches(nums: number[], n: number): number { let x = 1; let ans = 0; for (let i = 0; x <= n; ) { if (i < nums.length && nums[i] <= x) { x += nums[i++]; } else { ++ans; x *= 2; } } return ans; }