C++ | 100% | Time complexity O(N) | Easy | Math | Simple
Intuition\n Describe your first thoughts on how to solve this problem. \n\n\nThe goal is to ensure that we can form any number in the range [1, n] using the ele
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n![image.png](https://assets.leetcode.com/users/images/8fce702e-5d70-492f-a232-3a9b992deb31_1718520450.7429855.png)\n\nThe goal is to ensure that we can form any number in the range [1, n] using the elements in the given sorted array nums and possibly adding the minimum number of additional patches. The main idea is to keep track of the current sum of the numbers we can form, and whenever we find a gap (i.e., a number we cannot form with the current sum), we add the smallest number that fills this gap.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Initialize Variables:**\n**sum** to keep track of the current range of numbers we can form, initially set to 0.\n**ans** to count the number of patches needed, initially set to 0.\n\n**Edge Case Check:**\nIf the first element of nums is not 1, we need to patch 1 to start forming numbers from 1.\n\n**Iterate Through nums:**\nFor each number in nums, check if the next number we need to form (i.e., sum + 1) is less than the current number in nums. If so, we need to add patches until sum + 1 is not less than the current number in nums.\n\n**Add Patches:**\nCalculate the number of patches needed to bridge the gap using log2((nums[i] - 1) / (sum + 1)) + 1.\nUpdate sum and ans accordingly by adding patches.\n\n**Handle Remaining Gap:**\nAfter iterating through nums, if sum is still less than n, add the necessary patches to cover the remaining gap.\nReturn the Result:\n\nFinally, return the number of patches needed.\n\n# Complexity\n- Time complexity: O(N)\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# Code\n```\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        long long int sum=0;\n        int ans=0;\n        if(nums[0]!=1){\n            sum=1;\n            ans=1;\n        }\n        for(int i=0;i<nums.size();i++){\n            int val= sum+1;\n           if(sum>=n) return ans;\n            if(val<nums[i]){\n                  int numberAdded = log2((nums[i]-1)/val)+1;\n                for(int k=0;k<numberAdded;k++){\n                        sum+= val*pow(2,k);\n                        ans++;\n                        if(sum>=n) return ans;\n                    }\n                }\n            sum+= nums[i]; \n        }\n        if(sum<n){\n                int val= sum+1;\n                int numberAdded = log2(n/val)+1;\n                sum=sum+ val*(pow(2,numberAdded)-1)+n;\n                ans+= numberAdded;\n        }\n        return ans;\n    }\n};\n```
['C++']