Problem - Patching Array

Given a sorted array and a target $n$, find the minimum number of patches (additions) needed so that any number in $[1, n]$ can be formed as a sum of some elements. For $nums = [1,3]$, $n = 6$: you can make $\{1, 3, 4\}$ but not $2$, $5$, $6$. Add $2$ to make all of $[1, 6]$. Answer is $1$.

Think about what range of sums you can currently make, and what happens when you add a new number. Tricky: the array is sorted, which lets you process numbers in increasing order.

If you can make $[1, 5]$ and the next number is $7$, you cannot make $6$. Adding $6$ extends the range to $[1, 11]$ because you can now combine $6$ with existing sums.