LIKE CODING: MJ [4]

LIKE CODING: MJ [4]
Question: Give a set of coins denoted by an integer array a. a[i] is the value of the i-th coin which can be any integer. Find the minimal number of missing coins (whose value can be any integer) such that we can get any exact change from 1 to N by choosing from the new set of coins.

Example: If a = [1, 5] N=10, the missing coins in a are 2 and 4 because a subset of  [1, 2, 4, 5] can be summed to any integer from 1 to 10. Thus, the answer is 2.
http://www.mitbbs.com/article_t/JobHunting/33021821.html
给你一个int N，然后给你一个int[]，数组里每个元素只能用一次，要求通过加法得到
从1到N的所有数字，返回最少需要添加元素的个数

比如：N = 6，arr = [1, 3]。最少需要添加的元素个数就是1，因为我们只用添加2就
可以了, arr = [1,2,3]。这样所有1到6的元素都能被arr这个数组的subset相加得到。

注意不能使用产生的元素啊。比如说：arr = [1,3] 咱们可以产生4=1+3。 但是不能产
生5（5=4+1），这是非法的。

    vector<int> missing(int N, vector<int> a){

        sort(a.begin(), a.end());

        vector<int> output;

        int sum = 0; //sum of the first i coins

        int i = 0;

        while(true){

            if(i>=a.size() || a[i]>sum+1){

                output.push_back(sum+1);

                sum += sum+1;

            }else{

                sum += a[i];

                i++;

            }

            if(sum>N) break;

        }

        return output;

    }

};

    vector<int> a = {1,5};

    sol.missing(10, a);

Read full article from LIKE CODING: MJ [4]