1
class Solution {
2
 public:
3
  int minPatches(vector<int> &nums, int n) {
4
    nums.push_back(0);
5
    sort(nums.begin(), nums.end());
6
    long sum = 0;
7
    int ans = 0;
8
    for (int i = 1; i < nums.size(); i++) {
9
      while ((long)nums[i] > (long)(sum + 1)) {
10
        ans++;
11
        sum += (long)(sum + 1);
12
        if (sum >= (long)n) return ans;
13
      }
14
      sum += nums[i];
15
      if (sum >= (long)n) return ans;
16
    }
17
    while (sum < (long)n) {
18
      ans++;
19
      sum += (long)(sum + 1);
20
    }
21
    return ans;
22
  }
23
};