Leetcode Patching Array problem solution

YASH PAL,

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.

Leetcode Patching Array problem solution

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;
        int added = 0;
        
        while(R < n){
            if(i < nums.length && nums[i] <= R  + 1){
                R = R + nums[i];
                i++;
            } else {
                R += (R + 1);
                added++;
            }
        }
        
        return added;
    }
}

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;
}

coding problems solutions