1
// time complexity:
2
// while loop is - o(n) beacuse we can potentially get to n with nums array full of ones and we will pass on each of them
3
// in some cases it will hit o(logn) if the nums array is pretty empty
4
var minPatches = function (nums, n) {
5
  // nums is sorted so we don't have to sort it
6
  let index = 0;
7
  let sumCanCreate = 0;
8
  let patchCount = 0;
9
  while (sumCanCreate < n) {
10
    // if we can't create nums[index] or we at the end of nums and can't create n.
11
    // we can create nums[index] only if it is lower or equal to sumCanCreate+1.
12
    if (
13
      sumCanCreate + 1 < nums[index] ||
14
      (index >= nums.length && sumCanCreate + 1 < n)
15
    ) {
16
      patchCount++;
17
      // because we "patch" the next number in the sequence.
18
      sumCanCreate += sumCanCreate + 1;
19
      // if we can create nums[index].
20
    } else {
21
      // we can create anything from current sumCanCreate to (sumCanCreate + nums[index]).
22
      sumCanCreate += nums[index];
23
      index++;
24
    }
25
  }
26
  return patchCount;
27
};