Easy to understand solution | 100% Beast | Greedy Approach | c++ | python | java
Intuition\nThe problem requires ensuring that every integer in the range [1, n] can be formed by the sum of some subset of elements from the given sorted array 
# Intuition\nThe problem requires ensuring that every integer in the range [1, n] can be formed by the sum of some subset of elements from the given sorted array nums. If this is not possible, we need to determine the minimum number of additional numbers (patches) needed to achieve this.\n\nThe key intuition here is to maintain a running sum of the numbers that can be formed. By starting with the smallest number that cannot be formed (miss), we either use elements from nums if they can contribute to forming miss or patch the array by adding miss itself, thereby extending the range of numbers we can form.\n\n\n# Approach\n1. Initialization:\n   - ***\'miss\'*** is initialized to ***\'1\'***, representing the smallest number we need to form.\n   - ***\'i\'*** is initialized to ***\'0\'***, representing the current index in nums.\n   - ***\'patch\'*** is initialized to ***\'0\'***, representing the number of patches needed.\n\n2. Main Loop:\n   - The loop continues as long as ***\'miss\'*** is less than or equal to n.\n      - If the current element in ***\'nums\'*** is less than or equal to ***\'miss\'***, we can use this element to form miss and increment ***\'miss\'*** by the value of this element. We also move to the next element in nums by incrementing i.\n      - If the current element in nums is greater than ***\'miss\'*** or we have exhausted all elements in nums, we patch the array by adding ***\'miss\'*** to the range of numbers we can form and increment ***\'miss\'*** by ***\'miss\'***. We also increment the ***\'patch\'*** counter.\n# Complexity\n- Time complexity: **O(n)**, where ***\'n\'*** is the length of the nums array. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(1)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Example with Explanation:\nFor nums = [1, 2] and n = 10:\n\nStart with miss = 1, i = 0, patch = 0.\nnums[0] = 1 can form miss. Update miss = 1 + 1 = 2, increment i.\nnums[1] = 2 can form miss. Update miss = 2 + 2 = 4, increment i.\nNo more elements in nums, so patch with miss = 4. Update miss = 4 + 4 = 8, increment patch = 1.\nStill no more elements, patch with miss = 8. Update miss = 8 + 8 = 16, increment patch = 2.\nmiss = 16 is greater than n = 10, stop.\n\n**The minimum number of patches required is 2.**\n# Code\n```c++ []\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        int patch = 0;\n        long long miss = 1;\n        int i = 0;\n        \n        while(miss<=n){\n            if(i<nums.size() and nums[i] <= miss){\n                miss += nums[i];\n                i++;\n            }\n            else {   // if((i<nums.size() and nums[i]>miss) or i>nums.size())\n                patch++;\n                miss += miss;\n            }\n        }\n\n        return patch;\n    }\n};\n```\n```python []\nclass Solution:\n    def minPatches(self, nums: List[int], n: int) -> int:\n        patches = 0\n        miss = 1\n        i = 0\n        \n        while miss <= n:\n            if i < len(nums) and nums[i] <= miss:\n                miss += nums[i]\n                i += 1\n            else:\n                patches += 1\n                miss += miss\n        \n        return patches\n        \n```\n```Java []\nclass Solution {\n    public int minPatches(int[] nums, int n) {\n        int patches = 0;\n        long miss = 1;\n        int i = 0;\n\n        while (miss <= n) {\n            if (i < nums.length && nums[i] <= miss) {\n                miss += nums[i];\n                i++;\n            } else {\n                patches++;\n                miss += miss;\n            }\n        }\n\n        return patches;\n    }\n}\n```\n
['Array', 'Greedy', 'Python', 'C++', 'Java', 'Python3']