I see in many solutions posted here, the strategy is to patch the next missing number itself:
For example, with [1, 2, 3] and N=20, I get 1-6 covered, and I patch 7.
Yes, 7 would push the frontier the furthest (to 13), but if I choose to patch 4 instead, maybe a 4 may come in handy when I need to make other numbers down the road?
Why is this choice 7 optimal? Can any provide a solid proof?
I am wondering this too. Why adding 7 makes 7~13 covered? How to prove it for all general case? Especially during interview.
because before patching 7, 1~6 can already be covered. With 7 patched, now you are able to get 1+7, 2+7, 3+7,... 6+7. So next you just need to test whether 7+7 can be reached.
See the proof by contradiction here:
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.