[C++ | Python3 | JAVA] Easy Approach with simple solution
APPROACH\n Let us assume that we are on some ith element of the array.\n We were successfullly able to create each and every number till the range arr[i]-1 by t
**APPROACH**\n* Let us assume that we are on some `i`th element of the array.\n* We were successfullly able to create each and every number till the range `arr[i]-1` by taking some numbers from arr in the range `0` to `i-1`. \n* Hence after choosing `arr[i]` we can create numbers from `0` to `arr[i]-1 + arr[i]` . \n\t* Extra `arr[i]+1 to arr[i]+arr[i] -1` can be created by using `some numbers` and `arr[i]`\n* If we are able to create numbers upto `arr[i]-1` \n\t* No need to patch\n* Else \n\t* patch it with whatever numbers we are able to make +1 i.e `sum+1`\n\n\n**SOLUTION**\n`In C++`\n```\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        int m = nums.size() ;\n        long long i = 1, sum = 1 ,ans = 0 ;\n        if(nums[0] != 1)\n        {\n            ans++ ;\n            i--;\n        }\n        while(i < m && sum < n)\n        {\n            while(sum < nums[i]-1 && sum < n)\n            {\n                ans++ ;\n                sum += sum + 1 ;\n            }\n            sum += nums[i] ;\n            i++ ;\n        }\n        while(sum < n)\n        {\n            ans++ ;\n            sum += sum + 1 ;\n        }\n        return ans;\n    }\n}; \n```\n`In JAVA`\n```\nclass Solution {\n    public int minPatches(int[] nums, int n) {\n        int m = nums.length ;\n        int i = 1 , ans = 0 ;\n        long sum = 1 ;\n        if(nums[0] != 1)\n        {\n            ans++ ;\n            i-- ;\n        }\n        while(i < m && sum < n)\n        {\n            while(sum < nums[i]-1 && sum < n)\n            {\n                ans++ ;\n                sum = (sum<<1) + 1 ;\n            }\n            sum += nums[i] ;\n            i++ ;\n        }\n        while(sum < n)\n        {\n            ans++ ;\n            sum = (sum<<1) + 1;\n        }\n        return ans ;\n    }\n}\n```\n`In Python3`\n```\nclass Solution:\n    def minPatches(self, nums: List[int], n: int) -> int:\n        m = len(nums)\n        i = 1 \n        ans = 0\n        summ = 1\n        if nums[0] != 1:\n            ans+=1\n            i -= 1\n        while i < m and summ < n:\n            while summ < nums[i]-1 and summ < n:\n                ans+=1\n                summ += summ + 1\n                \n            summ += nums[i] \n            i+=1\n        while summ < n:\n            ans+=1\n            summ += summ + 1\n        return ans\n```
[]