Last updated on July 20th, 2024 at 04:21 am

Here, We see Patching Array LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Greedy

Companies

Google

Level of Question

Hard

Patching Array LeetCode Solution

Problem Statement

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

1. Patching Array LeetCode Solution C++

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
    int len = nums.size();
    int sum = 0;
    int patch = 0;
    int count = 0;
    while (sum < n) {
        if (count != len && nums[count] <= sum + 1) {
            sum += nums[count];
            count ++;
        }
        else {
            patch ++;
            if (sum > (INT_MAX - 1) / 2) {
                sum = INT_MAX;
            }
            else {
                sum = sum * 2 + 1;
            }
        }
    }
    return patch;        
    }
};

2. Patching Array LeetCode Solution Java

class Solution {
    public int minPatches(int[] nums, int n) {
    int count = 0;
    long priorSum = 0;
    for(int i=0; i<nums.length; i++) {
    	if(priorSum>=n) return count;
    	while(priorSum<n && nums[i]>priorSum+1) {
    		++count;
    		priorSum = (priorSum<<1) + 1;
    	}
    	priorSum += nums[i];
    }
    while(priorSum<n) {
    	++count;
    	priorSum = (priorSum<<1) + 1;
    }
    return count;        
    }
}

3. Patching Array LeetCode Solution JavaScript

var minPatches = function(nums, n) {
    var covered=1,count=0,i=0;
    while(covered<=n){
        if(i>=nums.length||covered<nums[i]){
            count++;
            covered+=covered;
        }else covered+=nums[i++];
    }
    return count;
};

4. Patching Array Solution Python

class Solution(object):
    def minPatches(self, nums, n):
        miss, i, added = 1, 0, 0
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                added += 1
        return added