Simple Greedy | TypeScript & JavaScript | Beats 100%
Intuition\nThe goal is to determine the minimum number of patches needed to ensure that the array can represent any number in the range [1, n] (inclusive). By g
# Intuition\nThe goal is to determine the minimum number of patches needed to ensure that the array can represent any number in the range **[1, n]** *(inclusive)*. By greedily selecting the smallest number possible to add to the array at each step, we aim to maximize the range covered by the array without unnecessarily increasing its size.\n\n---\n\n\n# Approach\n1. Initialize three variables: **additions** to keep track of the number of patches added, **i** as the index for the input array **nums**, and **sum** to track the cumulative sum covered by the current array.\n1. Iterate until the sum reaches or exceeds **n**:\n    - If the current element in **nums** can be added to the sum (i.e., **nums[i] <= sum + 1**), add it and move to the next element in **nums**.\n    - Otherwise, add the next number (i.e., **sum + 1**) to the array to cover the gap and increment **additions**.\nReturn the total number of additions made.\n\n---\n\n\n# Complexity\n- Time complexity:\nThe time complexity of this approach is $O(log (n))$ in the worst case. This is because at each step, we either increment **i** or double **sum**, which results in at most *log\u2082(n)* iterations.\n\n- Space complexity:\nThe space complexity is $O(1)$ as we are using only a constant amount of extra space for storing variables regardless of the input size.\n\n# Code\n```TypeScript []\nfunction minPatches(nums: number[], n: number): number {\n    let additions: number = 0, i: number = 0, sum: number = 0;\n\n    while (sum < n) {\n        if (i < nums.length && nums[i] <= sum + 1) {\n            sum += nums[i], i++;\n        }\n        else {\n            sum += sum + 1;\n            additions++;\n        }\n    }\n    return additions;\n};\n```\n```JavaScript []\nfunction minPatches(nums, n) {\n    let additions = 0, i = 0, sum = 0;\n\n    while (sum < n) {\n        if (i < nums.length && nums[i] <= sum + 1) {\n            sum += nums[i], i++;\n        }\n        else {\n            sum += sum + 1;\n            additions++;\n        }\n    }\n    return additions;\n};\n```\n\n
['Greedy', 'TypeScript', 'JavaScript']