[LC 330]. Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4]

用一个例子说明思路:
nums = [1, 2, 4, 13, 43], n = 100
miss — Smallest miss sum, i.e. sum in the range [0, miss) has been reached
miss = 1, nums[0] = 1, [0, 2) can be reached, miss -> 2
miss = 2, nums[1] = 2, [0, 4) can be reached, miss -> 4
miss = 4, nums[2] = 4, [0, 8) can be reached, miss -> 8
miss = 8, nums[3] = 13, add 8, [0, 16) can be reached, miss -> 16
miss = 16, nums[3] = 13, [0, 29) can be reached, miss -> 29
miss = 29, nums[4] = 43, add 29, [0, 58) can be reached, miss -> 58
miss = 58, nums[4] = 43, [0, 101) can be reached, miss -> 101 > 100

Added 2 numbers in total

    public int minPatches(int[] nums, int n) {
        long miss = 1; // n = Integer.MAX_VALUE时会用到long
        int i = 0, count = 0;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                count++;
                miss += miss;
            }
        }
        
        return count;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s