**Solution**

**Patching Array** https://leetcode.com/problems/patching-array/

**Algorithm**

- curr_sum refers to the sum that can be accomplished sequentially so far.
- next_sum = curr_sum+1.
- Assume next_sum = 7. curr_sum =6. nums[index] = any number less than 7. We can simply pick nums[index] and that makes sure we have covered next_sum. Why? Because we have combinations of [1,2,3,4,5,6] already covered. lowest value of nums[index] will be 1. maximum value will be 7. Say nums[index] = 5, then adding that will increase curr_sum to 6+5 = 11 (7 = 5+2, 8 = 5+3, 9 = %+4)...
- Now if nums[index] > next_sum, say it is 20. Then we need to add 7 as a patch. Now we can cover until 6 + 7 = 13.

```
class Solution(object):
def minPatches(self, nums, n):
"""
:type nums: List[int]
:type n: int
:rtype: int
"""
index, curr_sum, next_sum = 0, 0, 0
num_patches = 0
while curr_sum < n:
next_sum = curr_sum + 1
# Add the next element in the nums array
if index < len(nums) and nums[index] <= next_sum:
curr_sum, index = curr_sum + nums[index], index + 1
else:
# Add the next_sum as the next patc
num_patches = num_patches + 1
curr_sum = curr_sum + next_sum
return num_patches
```