Sponsored
Sponsored
This approach uses a greedy strategy to find the minimum number of patches required to cover the entire range [1, n]. Starting with a number missing initialized to 1, which represents the smallest sum we cannot form, we iterate through the array. If the current number in the array is less than or equal to missing, we increment our range to missing + nums[i]. Otherwise, we add missing to the array, effectively patching it, and increment our missing sum by itself.
Time complexity: O(m + log n) where m is the length of nums. The loop runs through nums and potentially adds new numbers until missing > n.
Space complexity: O(1), since no auxiliary space is used apart from a few variables.
1#include <vector>
2#include <iostream>
3using namespace std;
4
5class Solution {
6public:
7 int minPatches(vector<int>& nums, int n) {
8 int patches = 0, i = 0;
9 long missing = 1;
10 while (missing <= n) {
11 if (i < nums.size() && nums[i] <= missing) {
12 missing += nums[i++];
13 } else {
14 missing += missing;
15 patches++;
16 }
17 }
18 return patches;
19 }
20};
21
22int main() {
23 Solution s;
24 vector<int> nums = {1, 3};
25 int n = 6;
26 cout << s.minPatches(nums, n) << endl; // Output: 1
27 return 0;
28}The C++ solution utilizes a similar greedy strategy. It checks if each number in the sorted array can extend the known range of sums. If not, it patches the missing sum, then extends the range by using this patched value.