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