找出未吃树叶算法错误 [英] figure out Uneaten Leaves algorithm bug
问题描述
我在面试挑战中遇到了这个问题
I faced this problem in an interview challenge
K条毛毛虫正在吞噬N片叶子，每条毛毛虫
都掉下来了从叶到叶以独特的顺序排列，所有毛毛虫在位置0的小枝处开始
，然后落入
1和N之间的位置的叶子上。每个毛毛虫j都有一个关联的跳数Aj。跳数为j的
毛毛虫在j的
倍的位置吃树叶。它将按顺序j，2j，3j…进行。直到
到达叶子的尽头，它停下来建造它的茧。给定
a组A个K元素，我们需要确定未食用叶子的数量
。
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.
约束：
1< = N< = 10 9
1 <= N <= 109
1 <= K< = 15
1 <= K <= 15
1 <== A [i]< = 10 9
输入格式：
N =未食用的叶子数。
N = No of uneaten leaves.
K =毛毛虫的数量。
K = No. of caterpillars.
A =整数数组。
跳数输出：
A = Array of integer. jump numbers Output:
整数nu。未食用的叶子
The integer nu. Of uneaten leaves
样本输入：
10
3
2 < br>
4
5
10
3
2
4
5
输出：
4
说明：
[2，4，5]是3个成员的集合跳号。吃掉所有2、4和5的倍数的叶子。仅剩下编号分别为1,3,7,9的4张叶子。
[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.
解决此问题的幼稚方法是<全部N个数字的em> Boolean 数组，遍历每个毛毛虫，并记住它被吃掉的叶子。
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.
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;
}
此方法通过了10个测试案例中的8个，并给出了2个案例的错误答案。
另一种使用包含排除原则，对此的解释可以此处和这里
下面的
是我第二种方法的代码
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
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;
}
此方法仅通过了一个1/10测试用例。而对于其余测试用例，则超过了时间限制并给出了错误的答案。
问题：
我在第一种或第二种方法中缺少100％正确的内容。
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.
推荐答案
使用包含-排除定理是正确的方法，但是，您的实现似乎太慢了。我们可以使用位掩码技术来获得 O（K * 2 ^ K）时间复杂度。
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.
看看这个：
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;
}
第一种方法是 O（N * K）时间复杂度算法，N = 10 ^ 9并且K = 15，它将太慢，并且可能导致内存限制超过/时间限制超过。
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.
请注意， lcm 可以大于N，因此，需要附加检查。
Notice that lcm can be larger than N, so, additional check is needed.
这篇关于找出未吃树叶算法错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
