- some logic for checking if n can be formed from elements in nums
- if it cant, insert that element into the array
- increment the patch counter and recursively try again
*wrong*
🤔What Did I Struggle With?
recursion can work but the overhead in both memory and performance leads to an unacceptable solution
💡 Explanation of Solution
1. **Track the Smallest Missing Number**:
- Use a variable `miss` to track the smallest number that can't be formed yet, starting from `1`.
2. **Process the Array and Add Patches**:
- Go through the array while `miss <= n`:
- If the current number in the array can help cover `miss`, use it and extend the range.
- Otherwise, add `miss` to the array (a patch) to cover the gap, and update `miss` to double its value.
3. **Count the Patches**:
- Every time you add a patch, increment a counter. Once `miss > n`, return the counter.
This ensures all numbers in `[1, n]` can be formed with minimal additions.
⌛ Complexity Analysis
Time Complexity: O(len(nums) + log n)
Space Complexity: O(1)
💻 Implementation of Solution
class Solution {public: int minPatches(vector<int>& nums, int n) { long long miss = 1; // Start from the smallest number that needs to be formed int patches = 0, i = 0; // Use `i = 0` for zero-indexed arrays while (miss <= n) { if (i < nums.size() && nums[i] <= miss) { // Extend the range with the current number in nums miss += nums[i]; i++; } else { // Add a patch (the current `miss`) miss += miss; // Adding `miss` doubles the range patches++; } } return patches; }};