Patching Array - Algorithms and Problem SolvingAlgorithms and Problem Solving

Patching Array - Algorithms and Problem SolvingAlgorithms and Problem Solving

This is a Leetcode problem. Example 1: Return 1. Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch. Example 2: Return 2. Example 3: Return 0. Note that, we should construct all numbers from 1 to n. A dirty take on this problem would be to to go from 1 to n and add all the numbers missing in the array. But certainly this is not the optimal solution. Because we don't actually need all consecutive numbers to get another by adding them up. For example, A=[1,2,4]. In this case we don't need 3 to make 3 because we can make 3 by adding 1 and 2. Also we don't need 5 either. But if we want to make 8 then we have to add 8 in the list. Once we added 8 to the list i.e. A'=[1,2,4,8] then we don't need to add any more element until 15 (why?). Basically,

Read full article from Patching Array - Algorithms and Problem SolvingAlgorithms and Problem Solving