Simple intuitive and well-explained solution accepted as best in C
Before we hack this, we should be generous and think nothing about performance and try to come up with a sub-problem of it and then boot it from the beginning p
Before we hack this, we should be generous and think nothing about performance and try to come up with a sub-problem of it and then boot it from the beginning point.\n\nSo before we truly get started, let's suppose we are in a state where we can reach <font color="#ff0000">**top**</font> by its sub-array nums[0...i] then what should we consider for the next element nums[i+1]? \n\n - now we need to check if `nums[i+1]<=top+1` then update <font color="#ff0000">**top**</font> to **top+nums[i+1]** and move to the next element;\n\n - but if nums[i+1] is greater than top+1, then there is a gap (how many? God knows) between top and nums[i+1]; in this case we need to patch a number to the array, then what number it should be? As we have discussed, it should top+1 which will be the largest we can achieve now  **by patching** and then the top will be updated to **2*top+1**, right? Good, let's move on...\n - the generalised case have been discussed, then so what's the start? As we can easily get that the start value should be 1 then the top should be initialized to 0 and then everything just moves around! \n\n> End of the story!\n\nAs for the time cost, the nums array is limited and n is then determined by the **top = 2*top+1** equation, so O(logn) should be better to describe its time cost.\n\n - Space cost O(1)\n - Time cost O(logn)\n\n----------\n\n    int minPatches(int* nums, int size, int n)\n    {\n        int count=0, index=0;\n        long long top = 0;\n        while(top < n)\n        {\n            if(index<size && nums[index]<=(top+1))\n                top += nums[index++];\n            else\n            {\n                count++;\n                top = 2*top+1;\n            }\n        }\n        return count;\n    }
['Iterator']