Given a sorted list of positive integers arr and a positive integer target, determine the minimum number of additional positive integers (patches) that must be inserted into arr so that every integer in the range [1, target] can be represented as the sum of some subset of elements from arr (including the patches). Return the minimum number of patches required.
Example 1
Input: arr = [2, 4, 7], target = 15
Output: 2
Explanation: Add patches 1 and 8. Now all sums from 1 to 15 can be formed.
Example 2
Input: arr = [1, 2, 5], target = 10
Output: 1
Explanation: Add patch 4. Now all sums from 1 to 10 can be formed.
Example 3
Input: arr = [1, 3, 6], target = 8
Output: 1
Explanation: Add patch 2. Now all sums from 1 to 8 can be formed.
Constraints
Case 1
Input: arr = [1, 4, 5], target = 12
Expected: 2
Case 2
Input: arr = [1, 2, 3], target = 6
Expected: 0
Case 3
Input: arr = [3, 6, 9], target = 20
Expected: 3
Case 4
Input: arr = [2, 3, 7], target = 10
Expected: 2