最少添加数字 - 算法

Question

我在网上遇到过这个问题.

给定一个整数:N和一个数组int arr [],你必须在数组中添加一些元素,这样你就可以通过使用(添加)数组中的元素来生成从1到N.

请记住,在生成某个x(1 <= x <= N)时,您只能使用数组中的每个元素一次.返回最少添加数字的数量.

For example:

N=6, arr = [1, 3] 

1 is already in arr. 

add 2 to the arr. 

3 is already in arr 

4 = 1 + 3 

5 = 2 + 3 

6 = 1 + 2 + 3 

So we return 1 since we only need to add one element which is 2.

任何人都可以提供一些提示吗？

Answer 1

N1总是可以通过将 的子集添加到除和N - 1之外的数字来得到。因此，当数组中已经存在前一个连续元素时，必须进行编号。例子 -N = 2N = 1X1X - 1

    arr[] = {1, 2, 5}, N = 9
    ans := 0
    1 is already present.
    2 is already present.
    3 is absent. But prior 1 to (3 - 1) elements are present. So 3 is added in the array. But as 3 is built using already existed elements, so answer won't increase.
    same rule for 4 and 5

    So, ans is 0

    arr[] = {3, 4}, for any N >= 2

    ans = 2

    arr[] = {1, 3}, for any N >= 2

    ans = 1

因此，似乎只要 和1不2存在于数组中，我们就必须添加该元素，无论前面的元素是否已经在数组中。所有后面的数字都可以使用前面的元素组成。当尝试生成任何数字X(> 2) 时，我们已经在数组中找到了前面1的元素。X - 1所以X总是可以做出来的。

所以，基本上我们需要检查1和2是否存在。所以这个问题的答案不会大于2

约束2

在上面的算法中，我们假设，当数组中不存在新元素X但可以使用数组中已存在的元素来创建新元素时，答案不会增加，但X会添加到数组中以用于下一个数字构建。如果X无法添加到数组中怎么办？

那么，基本上就会变成一个子集和问题。对于每个缺失的数字，我们必须检查是否可以使用数组中元素的任何子集来生成该数字。这是一种典型的O(N^2)动态规划算法。

int subsetSum(vector<int>& arr, int N)
{
    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
    //  with sum equal to i
    bool subset[N + 1][arr.size() + 1];

    // If sum is 0, then answer is true
    for (int i = 0; i <= arr.size(); i++)
      subset[0][i] = true;

    // If sum is not 0 and set is empty, then answer is false
    for (int i = 1; i <= N; i++)
      subset[i][0] = false;

     // Fill the subset table in botton up manner
     for (int i = 1; i <= N; i++)
     {
       for (int j = 1; j <= arr.size(); j++)
       {
         subset[i][j] = subset[i][j - 1];
         if (i >= set[j - 1])
           subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
       }
     }

     unordered_map<int, bool> exist;
     for(int i = 0; i < arr.size(); ++i) {
         exist[arr[i]] = true;
     }

     int ans = 0;
     for(int i = 1; i <= N; ++i) {
          if(!exist[i] or !subset[i][arr.size()]) {
              ans++;
          }
     }

     return ans;
}