# 330. Patching Array

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: int minPatches(vector& nums, int n) { int ans = 0; int i = 0; // Point to nums long miss = 1; // Min sum in [1, n] we might miss while (miss <= n) if (i < nums.size() && nums[i] <= miss) { miss += nums[i++]; } else { // Greedily add miss itself to increase the range // From [1, miss) to [1, 2 * miss) miss += miss; ++ans; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int minPatches(int[] nums, int n) { int ans = 0; int i = 0; // Point to nums long miss = 1; // Min sum in [1, n] we might miss while (miss <= n) if (i < nums.length && nums[i] <= miss) { miss += nums[i++]; } else { // Greedily add miss itself to increase the range // From [1, miss) to [1, 2 * miss) miss += miss; ++ans; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def minPatches(self, nums: List[int], n: int) -> int: ans = 0 i = 0 # Point to nums miss = 1 # Min sum in [1, n] we might miss while miss <= n: if i < len(nums) and nums[i] <= miss: miss += nums[i] i += 1 else: # Greedily add miss itself to increase the range # From [1, miss) to [1, 2 * miss) miss += miss ans += 1 return ans