Python solution with detailed explanation


  • 0
    G

    Solution

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

    Algorithm

    1. curr_sum refers to the sum that can be accomplished sequentially so far.
    2. next_sum = curr_sum+1.
    3. 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)...
    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.