Leetcode Patching Array problem solution

YASH PAL, 31 July 202421 January 2026

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

Leetcode Patching Array 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

Patching Array 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 Leetcode Problems Solutions Leetcode

Leave a Reply