beats 100% in time,96% in space. | | easy to understand| |
Intuition\n Describe your first thoughts on how to solve this problem. \nthere is no intution i just wrote in page and got a pattern.\n# Approach\n Describe you
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**there is no intution i just wrote in page and got a pattern.**\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- we took `howmanypatch=0` to store number of elements to patch,`elementToSearch=1` we will search for this element as long as this doesnt equal to or greater then n.\n\n- we check if element exist in the array or not if it doesnt exist it means we need that element so in else statement we add that element in orginal element you can also multiply it by 2 `elementToSearch*=elementToSearch`.\n\n- if we pay attention lets suppose [1] as array max you can get is 1;\n- [1,2] max you can get is 3;\n- [1,2,4] max you can get is 7;\n- if you pay attention here when you put natural numbers in array in  non-decreasing manner and each next elment is 2* of last element,than you can create all the elements from [1,sumofallelements].\n- for example:[1,2,4,8,16,32] n=45 ,sum=63,you can create all the elements from range [1,63] as 45 comes in between we can also create it from these elements.\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 {\n    public int minPatches(int[] nums, int n) {\n        int howmanytopatch=0;\n        long elementToSearch=1;\n         \n         int lengthpointer=0;\n        while(elementToSearch<=n){\n      if(lengthpointer<nums.length && elementToSearch>=nums[lengthpointer]){\n        elementToSearch+=nums[lengthpointer];\n        lengthpointer++;\n      }\n      else{\n      howmanytopatch++;\n      elementToSearch+=elementToSearch;\n      }\n        }\n        return howmanytopatch;\n        \n    }\n}\n```
['Array', 'Dynamic Programming', 'Java']