找出Uneaten Leaves算法错误

I faced this problem in an interview challenge

我在面试挑战中遇到了这个问题

K caterpillars are eating their way through N leaves, each caterpillar falls from leaf to leaf in a unique sequence, all caterpillars start at a twig at position 0 and falls onto the leaves at position between 1 and N. Each caterpillar j has an associated jump number Aj. A caterpillar with jump number j eats leaves at positions that are multiple of j. It will proceed in the order j, 2j, 3j…. till it reaches the end of the leaves and it stops and build its cocoon. Given a set A of K elements , we need to determine the number of uneaten leaves.

K毛虫通过N片叶子进食，每只毛虫以独特的顺序从一片叶子落到另一片叶子，所有的毛虫都从0号位置的树枝开始落在1到N之间的叶子上。每只毛虫都有相关的跳跃数字Aj。具有跳号j的毛毛虫在j的倍数位置处吃叶子。它将以j，2j，3j ......的顺序进行。直到它到达叶子的末端，它停止并建立它的茧。给定一组K个元素，我们需要确定未吃叶子的数量。

Constraints:

约束：

1 <= N <= 10⁹

1 <= N <= 109

1 <= K <= 15

1 <= K <= 15

1 <= A[i] <= 10⁹

1 <= A [i] <= 109

Input format:

输入格式：

N = No of uneaten leaves.

N =没有未吃的叶子。

K = No. of caterpillars.

K =毛毛虫的数量。

A = Array of integer. jump numbers Output:

A =整数数组。跳数输出：

The integer nu. Of uneaten leaves

整数nu。未吃的叶子

Sample Input:

样本输入：

10
3
2
4
5

10 3 2 4 5

Output:

输出：

4

4

Explanation:

说明：

[2, 4, 5] is the 3-member set of jump numbers. All leaves which are multiple of 2, 4, and 5 are eaten. Only 4 leaves which are numbered 1,3,7,9 are left.

[2,4,5]是3个成员的跳跃数。所有叶子都是2,4和5的倍数。仅剩下4个编号为1,3,7,9的叶子。

the naive approach for solving this question is have a Boolean array of all N numbers, and iterate over every caterpillar and remember the eaten leaves by it.

解决这个问题的天真方法是有一个包含所有N个数字的布尔数组，并迭代每个毛虫并记住它吃掉的叶子。

int uneatenusingNaive(int N, vector<int> A)
{
    int eaten = 0;
    vector<bool>seen(N+1, false);
    for (int i = 0; i < A.size(); i++)
    {
        long Ai = A[i];
        long j = A[i];
        while (j <= N && j>0)
        {
            if (!seen[j])
            {
                seen[j] = true;
                eaten++;
            }
            j += Ai;
        }
    }
    return N - eaten;
}

this approach passed 8 out of 10 test cases and give wrong answer for 2 cases.

another approach using Inclusion Exclusion principle, explanation for it can be found here and here
below is my code for the second approach

这种方法通过了10个测试用例中的8个，并给出了2个案例的错误答案。另一种使用包含排除原理的方法，可以在这里找到它的解释，下面是我的第二种方法的代码

 int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a%b);
    }
    int lcm(int i, int j)
    {
        return i*j / gcd(i, j);
    }

    vector<vector<int>> mixStr(vector<vector<int>> & mix, vector<int>& A, unordered_map<int, int> & maxStart)
    {
        vector<vector<int>> res;
        if (mix.size() == 0)
        {
            for (int i = 0; i < A.size(); i++)
            {
                vector<int> tmp;
                tmp.push_back(A[i]);
                res.push_back(tmp);
            }
            return res;
        }


        for (int i = 0; i<mix.size(); i++)
        {
            int currSlotSize = mix[i].size();
            int currSlotMax = mix[i][currSlotSize - 1];

            for (int j = maxStart[currSlotMax]; j < A.size(); j++)
            {
                vector<int> tmp(mix[i]);
                tmp.push_back(A[j]);
                res.push_back(tmp);
            }
        }
        return res;
    }
    int uneatenLeavs(int N, int k, vector<int> A)
    {
        int i = 0;
        vector<vector<int>> mix;
        bool sign = true;
        int res = N;
        sort(A.begin(), A.end());
        unordered_map<int,int> maxStart;
        for (int i = 0; i < A.size(); i++)
        {
            maxStart[A[i]] = i + 1;
        }
        int eaten = 0;


        while (mix.size() != 1)
        {   

            mix = mixStr(mix, A, maxStart);
            for (int j = 0; j < mix.size(); j++)
            {
                int _lcm = mix[j][0];
                for (int s = 1; s < mix[j].size(); s++)
                {
                    _lcm = lcm(mix[j][s], _lcm);
                }
                if (sign)
                {
                    res -= N / _lcm;
                }
                else
                {
                    res += N / _lcm;
                }
            }
            sign = !sign;
            i++;
        }
        return res;
    }

this approach passed only one 1/10 test case. and for the rest of test cases time limit exceeded and wrong answer.

Question:
What am I missing in first or second approach to be 100% correct.

这种方法只通过了一个1/10的测试用例。并且对于其余的测试用例超出时间限制并且错误答案。问题：在第一种或第二种方法中我缺少的是100％正确。

1 个解决方案

#1

Using Inclusion-Exclusion theorem is correct approach, however, your implementation seems to be too slow. We can use bitmasking technique to obtain a O(K*2^K) time complexity.

使用包含 - 排除定理是正确的方法，但是，您的实现似乎太慢。我们可以使用比特掩码技术来获得O（K * 2 ^ K）时间复杂度。

Take a look at this:

看看这个：

long result = 0;

for(int i = 1; i < 1 << K; i++){
     long lcm = 1;
     for(int j = 0; j < K; j++)
        if(((1<<j) & i) != 0) //if bit j is set, compute new LCM after including A[j]
           lcm *= A[j]/gcd(lcm, A[j]);
     if(number of bit set in i is odd)
        result += N/lcm;
     else
        result -= N/lcm; 
}

For your first approach, an O(N*K) time complexity algorithm, with N = 10^9 and K = 15, it will be too slow, and can cause memory limit exceed/time limit exceed.

对于您的第一种方法，O（N * K）时间复杂度算法，N = 10 ^ 9且K = 15，它将太慢，并且可能导致内存限制超出/超出时限。

Notice that lcm can be larger than N, so, additional check is needed.

请注意，lcm可能大于N，因此需要进行额外检查。

#1