@@ -0,0 +1,1307 @@
+/**%0A * Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in%0A * range %5B1, n%5D inclusive can be formed by the sum of some elements in the array.%0A * Return the minimum number of patches required.%0A *%0A * Example 1:%0A * nums = %5B1, 3%5D, n = 6%0A * Return 1.%0A *%0A * Combinations of nums are %5B1%5D, %5B3%5D, %5B1,3%5D, which form possible sums of: 1, 3, 4.%0A * Now if we add/patch 2 to nums, the combinations are: %5B1%5D, %5B2%5D, %5B3%5D, %5B1,3%5D, %5B2,3%5D, %5B1,2,3%5D.%0A * Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range %5B1, 6%5D.%0A * So we only need 1 patch.%0A *%0A * Example 2:%0A * nums = %5B1, 5, 10%5D, n = 20%0A * Return 2.%0A * The two patches can be %5B2, 4%5D.%0A *%0A * Example 3:%0A * nums = %5B1, 2, 2%5D, n = 5%0A * Return 0.%0A *%0A * Tags: Greedy%0A */%0Apublic class PatchingArray %7B%0A%0A    /**%0A     * Build the largest range possible and find the smallest missing number%0A     * if missing %3E= nums%5Bi%5D, range can be extended to missing + nums%5Bi%5D%0A     * else add missing number, range can be extended to missing * 2%0A     * stop till missing %3E n%0A     */%0A    public int minPatches(int%5B%5D nums, int n) %7B%0A        int total = 0, i = 0;%0A        for (long miss = 1; miss %3C= n; total++) %7B%0A            miss += (i %3C nums.length && nums%5Bi%5D %3C= miss) ? nums%5Bi++%5D : miss;%0A        %7D%0A        return total - i;%0A    %7D%0A%7D%0A

add 330 Patching Array