Patching Array https://leetcode.com/problems/patching-array/
- 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