# Leetcode Patching Array problem solution

In this Leetcode Patching Array problem solution you are 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.

## Problem solution in Python.

```def minPatches(self, nums: List[int], n: int) -> int:
if nums == []:
Span, Min = 1, 1
while Span < n:
Span = 2*Span + 1
Min = Min + 1

return Min
Min, Span, i = 0, 0, 0
if nums[0] == 1:
Span, i = 1, 1

while i < len(nums) and Span < n:
if nums[i] > Span + 1:
Span = 2*Span + 1
Min = Min + 1
else:
Span = Span + nums[i]
i = i + 1
while Span < n:
Span = 2*Span + 1
Min = Min + 1

return Min
```

## Problem solution in Java.

```class Solution {
public int minPatches(int[] nums, int n) {
long R = 0;
int i = 0;

while(R < n){
if(i < nums.length && nums[i] <= R  + 1){
R = R + nums[i];
i++;
} else {
R += (R + 1);
}
}

}
}
```

## Problem solution in C++.

```class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int m=nums.size();
long long i=1,sum=1,ans=0;
if(nums[0]!=1)
ans++,i=0;

for(i;i<m && sum<n;i++){
while(sum<nums[i]-1 && sum<n){
ans++;
sum+=sum+1;
}
sum+=nums[i];
}
while(sum<n ){
ans++;
sum+=sum+1;
}
return ans;
}
};
```

## Problem solution in C.

```int leadingsetbitPos(int n){
int pos = -1;
for(int i = 0; i < 32; i++){
if(n&0x1 == 1){
pos = i;
}
n = n >> 1;
}
return pos;
}

int minPatches(int* nums, int numsSize, int n){
int count = 0;
long long Maxreachable = 0;

if(numsSize == 0){ return (1 + leadingsetbitPos(n)); }
if(numsSize == 1) {return leadingsetbitPos(n); }

if(nums[0] != 1 ){ count += 1; }
if(nums[0] == 1 ){ count += 0; }
Maxreachable += 1;
int iterator = 1-count;
while(iterator < numsSize && Maxreachable < n){
if(nums[iterator] <= Maxreachable+1){
Maxreachable += nums[iterator];
iterator++;
}else{
count++;
Maxreachable += Maxreachable+1;
}

if(Maxreachable >= n){
return count;
}
}

while(Maxreachable < n){
Maxreachable += Maxreachable+1;
count++;
}
return count;
}
```