1ms Java solution with explain
public int minPatches(int[] nums, int n) {\n        int index = 0;\n        int addedCount = 0;\n        long canReachTo = 0;\n        while( canReachTo < n){\n
    public int minPatches(int[] nums, int n) {\n        int index = 0;\n        int addedCount = 0;\n        long canReachTo = 0;\n        while( canReachTo < n){\n            if( nums.length > index){\n                int nextExisting = nums[index];\n                if(nextExisting == canReachTo + 1){\n                    canReachTo = (canReachTo << 1) + 1;\n                    index++;\n                } else if(nextExisting > canReachTo + 1){\n                    addedCount++;\n                    canReachTo = (canReachTo << 1) + 1;\n                } else {\n                    canReachTo = nextExisting + canReachTo;\n                    index++;\n                }\n            } else {\n                addedCount++;\n                canReachTo = (canReachTo << 1) + 1;\n            }\n        }\n        return addedCount;\n    }\n\nThis solution is based on greedy method. \nFor example, if you have 1, 2, it can reach 2+(2-1) = 3. So when we want to add up to 4, we have to add 4 into the list. And 1,2,4 can reach to 4+(4-1). \nSimilarly, for any added number n, they can add up to n+(n-1) without missing one number. \nIf there is one number x which satisfies n < x < n+(n-1), then we don't have to worry about the numbers until x + n + n - 1. Repeatedly evaluate the next number that the list of numbers can reach to, and add into the list next one when missing.\nSo basically this method is <log(n) time complexity and O(1) space complexity.
[]