Given a sorted array and a target , find the minimum number of patches (additions) needed so that any number in can be formed as a sum of some elements. For , : you can make but not , , . Add to make all of . Answer is .
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 and the next number is , you cannot make . Adding extends the range to because you can now combine with existing sums.