✅ Beginner Friendly with detailed Explanation
Intuition\nWhen dealing with an array of integers, the goal is to determine the minimum number of patches (additional numbers) required so that every number fro
# Intuition\nWhen dealing with an array of integers, the goal is to determine **the minimum number of patches (_additional numbers_)** required so that every number from 1 to `n` can be formed by the sum of some subset of the array. Initially, it seems feasible to check all combinations, but this would be inefficient. Instead, we can use a greedy approach to iteratively cover the next missing number.\n\n# Approach\n1. **Initialization**:\n   - Start with `missingNumber` set to 1. This variable represents the smallest number that cannot currently be formed using the numbers in the array or the patches added.\n   - Use `patchesCount` to count the number of patches (new numbers) added.\n   - Use `index` to iterate through the `nums` array.\n\n2. **Iterate Until All Numbers Up to `n` Can Be Formed**:\n   - Continue the loop while `missingNumber` is less than or equal to `n`.\n   - If the current number in `nums` (at `index`) is less than or equal to `missingNumber`, add this number to `missingNumber` (since it helps cover the missing number) and increment the `index`.\n   - If the current number in `nums` is greater than `missingNumber`, add `missingNumber` itself to cover the gap. This doubles `missingNumber` and increments `patchesCount` since we added a new patch.\n\n3. **Return the Result**:\n   - After the loop, `patchesCount` will contain the number of patches added to ensure all numbers from 1 to `n` can be formed.\n\n# Complexity\n- **Time Complexity**: \n  - $$O(m)$$ where $$m$$ is the length of the input array `nums`.\n  - The loop runs as long as `missingNumber` is less than or equal to `n`, but in each iteration, either `missingNumber` is doubled, or an element from `nums` is used. Hence, the while loop will run at most `m + log(n)` times.\n\n- **Space Complexity**:\n  - $$O(1)$$ as we only use a few extra variables (`missingNumber`, `patchesCount`, and `index`) regardless of the input size.\n\n# Swift Code\n```swift []\nclass Solution {\n    func minPatches(_ nums: [Int], _ n: Int) -> Int {\n        var missingNumber: Int = 1  // The smallest number that cannot be formed\n        var patchesCount: Int = 0   // Number of patches (numbers) added\n        var index: Int = 0          // Index to iterate through the nums array\n        \n        // While the missing number is less than or equal to n\n        while missingNumber <= n {\n            // If the current number in nums can be used to form the missing number\n            if index < nums.count && nums[index] <= missingNumber {\n                // Use nums[index] to cover the missing number and increment the index\n                missingNumber += nums[index]\n                index += 1\n            } else {\n                // Add the missing number itself to the range to cover the gap\n                missingNumber += missingNumber\n                patchesCount += 1\n            }\n        }\n        \n        // Return the number of patches added\n        return patchesCount\n    }\n}\n```
['Array', 'Greedy', 'Swift']