O(k+log(N)) time O(1) space java with explanation
Iterating the nums[], while keep adding them up, and we are getting a running sum starting from 0. At any position i, if nums[i] > sum+1, them we are sure we ha
Iterating the nums[], while keep adding them up, and we are getting a running sum starting from 0. At any position i, if nums[i] > sum+1, them we are sure we have to patch a (sum+1) because all nums before index i can't make sum+1 even adding all of them up, and all nums after index i are all simply too large. Since the sum is growing from 0, we also can be sure that any number equal or smaller than the current sum is covered.\n\nIn the worst case, the code will go thru all the numbers in the array before the sum goes doubling itself towards n. Therefore, the time is O(k+log(n)) where k being the size of the array and n being the target n to sum up. Thanks @StefanPochmann for pointing it out.\n\nHere is the accepted code,\n\n    public class Solution {\n        public int minPatches(int[] nums, int n) {\n            long sum = 0;\n            int count = 0;\n            for (int x : nums) {\n                if (sum >= n) break;\n                while (sum+1 < x && sum < n) { \n                    ++count;\n                    sum += sum+1;\n                }\n                sum += x;\n            }\n            while (sum < n) {\n                sum += sum+1;\n                ++count;\n            }\n            return count;\n        }\n    }
['Array', 'Java']