[C++ Solution ] Detailed explanation -- greedy
Let\'s start from an example, the given vector input = {1, 4, 6, 10}, n = 20;\n\nSince we are aimed to cover all the numbers in range [1, 20], let\'s consider t
Let\'s start from an example, the given vector input = {1, 4, 6, 10}, n = 20;\n\nSince we are aimed to cover all the numbers in range [1, 20], let\'s consider the elements one by one.\nWe may create an aiding vector<int> aid, which is used to contain all the elements that have been covered SO FAR.\nOf course, this "aid" is empty from the begining. What\'s more, use a counter to count how many extra elements should we provide, i.e. the output. \n\nFirstly, we expect the first element "1" to be added into the aid. After check the input vector, we find we have an "1", so just use it add it into our "aid" vector;\naid = {1} so far, count = 0\n\nNext, we expect "2" to be added. Looking at the input vector, since the first element has already been used, we check from the second element, which is "4". Apparently, we need to patch one extra element to get the expected "2". \nNow the problem comes, should we directly give a "2" or we may give an "1" since 1+1 also yeilds "2". The answer is that both ways work, HOWEVER, "2" is a better choice since 1+2 gives 3, adding a "2" expand aid into {1,2,3} while adding an "1" just turns aid = {1,2}. So we patch a "2", and the count++; BTW, this this can be though as "greedy strategy"\naid = {1,2,3} so far, count =1\n\nAfter that, we expect "4". Checking input, we find a 4 and so there\'s no need for extra patching. Add 4 into the aid would expand it into {1, 2, 3 ,4 ,1+4, 2+4, 3+4}. You may have notice that\n\n#### adding an element x would incrase the size of the aid vector by x. \n\naid = {1,2,3,4,5,6,7} so far, count = 1\n\nThen we expect 8, searching the input vector, the next element not used is "6", since we may use the "2" in aid vector to add 6 and get 8, so it meets our needs. What\'s more, as said before, the "6" would expand our aid vector into {1, 2, 3, 4, 5, 6, 7, 2+6, 3+6, 4+6, 5+6, 6+6, 7+6}.\naid = {1,2,3,4,5,6,7,8,9,10,11,12,13} by now, count = 1\n\nThe next expected element is 14, and the next element provided by input is "10", again, this would turn our aid vector into {1,2,3,....,23} and we notice that 23 > 20, which means the task is completed.\n\n\nLooking back the whole process, we could easily draw two conclucions:\n#### 1. We only need to patch when the next element that the input vector offers is bigger that what we expect. When this circumstance occurs, just patch the desired element and add it into aid vector.\n#### 2. Once we add an element x to aid vector, no matter whether it\'s provided by input vector or patching, the aid vector\'s size increase x, which would turn the next "expected value" into "current expected value + x". When the next expected value > n, the task is finished.\n\nActually, why do we need an aid vector? We can just use the "expected value" to indicate the aid vector we have, since aid vector = [1, expected value - 1]. This yeilds my final result:\n\n```\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        int index = 0;\n        int count = 0;\n        if(nums[0]>1){\n            ++count;   \n        }\n        else{\n            ++index;\n        }\n        long long expect = 2;\n        while(expect <= n){\n            if(index>=nums.size() || nums[index]>expect){\n                // need to add this number\n                ++count;\n                // expect += expect -> expect<<1\n                expect = expect<<1;  \n            }\n            else{\n                // expand the range\n                expect += nums[index];\n                ++index;\n            }\n        }\n        return count;\n    }\n};\n```\n\n\n
['C++']