[leetcode #330] Patching Array

Problem

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

Example 1:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
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:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

Constraints:

・ 1 <= nums.length <= 1000
・ 1 <= nums[i] <= 10⁴
・ nums is sorted in ascending order.
・ 1 <= n <= 2³¹ - 1

Idea

이번 문제도 풀지 못 했다. 처음엔 주어진 값을 running sum을 이용해 계산한 후 set에 넣고 빈 값을 채우려고 했는데, 빈 값을 찾는게 어려워 배보다 배꼽이 더 큰 격이 되어버렸다. 답을 찾아보니 의외로 간단했다.

nums로 주어진 값을 순차적으로 탐색하면서 없는 값을 계산하는데, 없는 값이 탐색하고 있는 nums의 값보다 작거나 같을 경우 patch하는 값이 된다. [1,5,10]을 예로 들어보자. 없는 값을 miss로 하고 처음에 1로 설정을 한다.

miss = 1, nums[0] = 1 → nums[0] ≦ 1
next miss → nums[0] + miss = 2
nums[0] → nums[1]

이럴 경우 1이 이미 있으므로 patch할 필요가 없다. 다음 탐색할 대상은 miss + nums[0]인 2가 된다.

miss = 2, nums[1] = 5 → nums[1] > 2
patch → 2
next miss → miss + miss = 4

nums[1]이 2보다 크므로 2를 만들 방법이 없다. 따라서 2는 반드시 patch해야 할 대상이 된다. patch한 수로 miss인 값을 만들었으면 다음으로 채워야 할 값은 miss의 2배가 된다. 왜냐하면 miss보다 작은 수는 이미 다른 수들의 조합으로 만들 수 있기 때문에 miss * 2보다 작은 수도 전부 만들 수 있다.

miss = 4, nums[1] = 5 → nums[1] > 4
patch → 4
next miss → miss + miss = 8

4도 없으므로 4도 patch를 하고 8을 만들 수 있는지 확인한다.

miss = 8, nums[1] = 5 → nums[1] ≦ 8
next miss → miss + 5 = 13
nums[1] → nums[2]

1~7까지를 만들 수 있는데 nums[1]이 5이므로 1~12까지의 수도 만들 수 있다.

miss = 13, nums[2] = 10 → nums[2] ≦ 13
next miss → miss + 10 = 23

1~12까지의 수를 만들 수 있는데 nums[2]가 10이므로 1~22까지의 수도 만들 수 있다.
n이 20이므로 2와 4만 patch하면 1~20까지의 수를 조합해서 만들 수 있다.

알고리즘은 다음과 같다.

1. 채워야 할 수 (miss)를 1으로 설정한 뒤 nums를 탐색한다.
2. miss가 n보다 작거나 같을 때까지 탐색한다.
   a. 현재 탐색하는 array의 값이 miss보다 작거나 같을 경우 miss에 해당 값을 더하고 다음 값으로 넘어간다.
   b. 현재 탐색하는 array의 값이 miss보다 클 경우 miss에 miss를 더하고 patch count를 증가시킨다.
3. 탐색이 끝난 뒤 patch count를 리턴한다.

문제를 풀고 나니 너무 재미있었던 문제라는 생각이 들었다. 이런 방식으로 문제를 풀 수 있다니!

Solution

class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
    	int count = 0;
        int i = 0;

        while(miss <= n){
            if(i<nums.length && nums[i] <= miss){
                miss = miss + nums[i];
                i++;
            }else{
                miss += miss;
                count++;
            }
        }

        return count;
    }
}

Reference

https://leetcode.com/problems/patching-array/