1
class Solution {
2
  public int minPatches(int[] nums, int n) {
3
    long sum = 0;
4
    int count = 0;
5
    for (int x : nums) {
6
      if (sum >= n) break;
7
      while (sum + 1 < x && sum < n) {
8
        ++count;
9
        sum += sum + 1;
10
      }
11
      sum += x;
12
    }
13
    while (sum < n) {
14
      sum += sum + 1;
15
      ++count;
16
    }
17
    return count;
18
  }
19
}