Find out the error of the Uneaten Leaves algorithm

Question

I encountered this problem in an interview

K caterpillars travel through N leaves, each caterpillar falls from leaf to leaf in a unique sequence, all caterpillars start on a branch at position 0 and fall on leaves at a position between 1 and N. Each caterpillar j has a connected number of jumps Aj. hopping caterpillar eats leaves at positions that are a multiple of j. He will act in the order j, 2j, 3j .... it comes to the end of the leaves, and he stops and builds his cocoon. Given a set A of elements K, we need to determine the number of uneaten leaves.

Limitations:

1 <= N <= 10 ⁹

1 <= K <= 15

1 <= A [i] <= 10 ⁹

Input format:

N = No uneaten leaves.

K = Number of tracks.

A = array of integer. transition numbers. Exit:

The integer nu. From uneaten leaves

Input Example:

10
3
2
4
5

Output:

4

Explanation:

[2, 4, 5] - 3-member set of transition numbers. All leaves divisible by 2, 4, and 5 are eaten. Only 4 sheets remained, numbered 1,3,7,9.

A naive approach to solving this issue is to have a Boolean array of all N numbers and iterate over each caterpillar and remember about food.

 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 gave the wrong answer for 2 cases.

another approach using the inclusion exclusion principle , an explanation for this 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; } 

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

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

Answer 1

Using the inclusion-exclusion theorem is the right approach, however, your implementation seems too slow. We can use the bit masking method to get the 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, the O (N * K) complexity algorithm, with N = 10 ^ 9 and K = 15, will be too slow and may cause the memory limit to exceed / exceed the time limit.

Please note that lcm may be larger than N, so additional verification is needed.