*Java* here is my greedy version with brief explanations (1ms)
Greedy idea: add the maximum possible element whenever there is a gap\n\n    public int minPatches(int[] nums, int n) {\n        int count = 0;\n        long pr
Greedy idea: add the maximum possible element whenever there is a gap\n\n    public int minPatches(int[] nums, int n) {\n        int count = 0;\n        long priorSum = 0; // sum of elements prior to current index\n        for(int i=0; i<nums.length; i++) {\n        \tif(priorSum>=n) return count; // done\n        \twhile(priorSum<n && nums[i]>priorSum+1) { // whenever there is a gap between priorSum and current value, add elements in a greedy manner\n        \t\t++count;\n        \t\tpriorSum = (priorSum<<1) + 1;\n        \t}\n        \tpriorSum += nums[i];\n        }\n        while(priorSum<n) {\n        \t++count;\n        \tpriorSum = (priorSum<<1) + 1;\n        }\n        return count;\n    }\n\nThe above one can be further simplified to one-pass as follows:\n\n    public int minPatches(int[] nums, int n) {\n        int count = 0, i = 0;\n        long priorSum = 0;\n        while(priorSum<n) {\n            if(i>=nums.length || nums[i]>priorSum+1) {\n                ++count;\n                priorSum = (priorSum<<1) + 1;\n            }\n            else priorSum += nums[i++];\n        }\n        return count;\n    }
['Java']