Tap here to switch tabs
Problem
Submissions

Problem: Patching Array

Patching Array gives you a sorted array and a target limit, then asks for the fewest added values so every number from one through the limit can be made by subset sums.

Statement

Given a sorted integer array nums and an integer n, return the minimum number of elements that must be added to the array such that every number in the range [1,n][1, n] inclusive can be formed by the sum of a subset of elements from nums.

Constraints:

  • 1≤1 \leq nums.length ≤1000\leq 1000

  • 1≤1 \leq nums[i] ≤104\leq 10^4

  • nums is sorted in ascending order.

  • 1≤1 \leq n ≤231−1\leq 2^{31} - 1

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Patching Array

Patching Array gives you a sorted array and a target limit, then asks for the fewest added values so every number from one through the limit can be made by subset sums.

Statement

Given a sorted integer array nums and an integer n, return the minimum number of elements that must be added to the array such that every number in the range [1,n][1, n] inclusive can be formed by the sum of a subset of elements from nums.

Constraints:

  • 1≤1 \leq nums.length ≤1000\leq 1000

  • 1≤1 \leq nums[i] ≤104\leq 10^4

  • nums is sorted in ascending order.

  • 1≤1 \leq n ≤231−1\leq 2^{31} - 1