# Patching Array LeetCode Solution

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

## 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

## Patching Array LeetCode SolutionC++

``````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;
}
};```Code language: PHP (php)```

## Patching Array LeetCode SolutionJava

``````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;
}
}```Code language: PHP (php)```

## Patching Array LeetCode SolutionJavaScript

``````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;
};```Code language: JavaScript (javascript)```

## Patching Array SolutionPython

``````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