leetcode/problems-cpp/patching-array/solution.h at main · goodstudyqaq/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class Solution {
   public:
    int minPatches(vector<int>& nums, int n) {
        int sz = nums.size();

        long long now = 0;
        int ans = 0;

        for (int i = 0; i < sz && now < n; i++) {
            int val = nums[i];
            if (val <= now + 1) {
                now += val;
            } else {
                ans++;
                now = now + now + 1;
                i--;
            }
        }
        while (now < n) {
            ans++;
            now = now * 2 + 1;
        }
        return ans;
    }
};