Force deduction exercise - 29 complete the array as required

29 Complete the array as required

1. Problem description
Given a sorted array of positive integers nums, And a positive integer n . from [1, n] Select any number in the interval and add it to nums in , bring [1, n] Any number in the interval can be used nums The sum of some numbers in . Please output the minimum number of numbers that need to be supplemented to meet the above requirements .

Example 1:

Input : nums = [1,3], n = 6

Output : 1

explain :

according to nums The existing combination in [1], [3], [1,3], We can draw 1, 3, 4.

Now if we will 2 Add to nums in , Combination becomes : [1], [2], [3], [1,3], [2,3], [1,2,3].

The sum of them can represent numbers 1, 2, 3, 4, 5, 6, Be able to cover [1, 6] All the numbers in the interval .

So we need to add at least one number .

Example 2:

Input : nums = [1,5,10], n = 20

Output : 2

explain : We need to add [2, 4].

Example 3:

Input : nums = [1,2,2], n = 5

Output : 0
2. Enter description
First, enter the length of the array m, Then input m It's an integer .

Finally, enter a positive integer n.

n No more than 32 position int The representation range of type , namely ：n<=2147483647.
3. The output shows that
Output an integer
4. Example
Input
3
1 5 10
20
Output
2
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<stack>
using namespace std;

int min_Patches(vector<int> &nums, int sum)
{
    
	// requirement ：
	// Given a sorted array of positive integers  nums, from  [1, n]  Select any number in the interval and add it to  nums  in , bring  [1, n]  Any number in the interval can be used  nums  The sum of some numbers in .
	// Please output the minimum number of numbers that need to be supplemented to meet the above requirements .

	// Problem solving  https://leetcode.cn/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1/
	// about x, if [1,x-1] All numbers are overwritten , And x In the array , be [1,2*x-1] All numbers are also overwritten 

	//1. Definition 
	long long total = 1;// The cumulative sum 
	int index = 0;// Ergodic subscript 
	int count = 0;// The number of numbers to be added 

	//2. Traversal and processing 
   
	// Every time an array is not found  nums  The smallest integer covered  x, Add  x, Then find the next smallest integer that is not covered , Repeat the above steps until the interval  [1,n]  All numbers in are overwritten .

	while (total <= sum)
	{
    
		if (index < nums.size() && nums[index] <= total )
		{
    
			total += nums[index++];
		}
		else 
		{
    
			total = total * 2;
			count++;// Add one to the number that needs to be supplemented 
		}
	}

	return count;
}


 
int main()

{
    
	vector<int>nums;
	int m,tmp,n;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
    
		cin >> tmp;
		nums.push_back(tmp);
	}
	cin >> n;
	int res = min_Patches(nums, n);
	cout << res << endl;
	return 0;
}