Patching Array – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• nums is sorted in ascending order.
• 1 <= n <= 231 - 1

C++  Patching Array  LeetCode Solution

class Solution {
public:
int minPatches(vector<int>& nums, int n) {
    int cnt=0,i=0;
    long long maxNum=0;
    while (maxNum<n){
       if (i<nums.size() && nums[i]<=maxNum+1)
            maxNum+=nums[i++];
       else{
            maxNum+=maxNum+1;cnt++;
       }
   }
   return cnt;
}
};

Java  Patching Array LeetCode Solution

public static int minPatches(int[] nums, int n) {
	long max = 0;
	int cnt = 0;
	for (int i = 0; max < n;) {
		if (i >= nums.length || max < nums[i] - 1) {
			max += max + 1;
			cnt++;
		} else {
			max += nums[i];
			i++;
		}
	}
	return cnt;
}
 

Python 3  Patching Array LeetCode Solution

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        covered,res,i=0,0,0
        while covered<n:
            num=nums[i] if i<len(nums) else math.inf
            if num>covered+1:
                covered=covered*2+1
                res+=1
            else:
                covered+=num
                i+=1       
        return res

Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1

Leave a comment below

Related posts:

LeetCode All Array Solution List – all in one place Remove Duplicates from Sorted Array – LeetCode Solution Find First and Last Position of Element in Sorted Array – LeetCode Solution Search in Rotated Sorted Array – LeetCode Solution Find Minimum in Rotated Sorted Array – LeetCode Solution Two Sum II – Input Array Is Sorted – LeetCode Solution