Last updated on October 5th, 2024 at 09:27 pm

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*

*List of all LeetCode Solution*

## Topics

Greedy

## Companies

## Level of Question

Hard

**Patching Array LeetCode Solution**

## Table of Contents

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