# Caterpillar uneaten leaves

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 as 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 K<-15, N<=10^9, we need to determine the number of uneaten leaves.

Input:

• N = No of uneaten leaves
• K = No. of caterpillars
• A = Array of integer jump numbers

Output:

The integer nu. Of uneaten leaves

Sample Input:

10
3
2
4
5


Output:

4


Explanation:

[2, 4, 5] is a j member jump numbers, all leaves which are multiple of 2, 4, and 5 are eaten, leaves 1,3,7,9 are left, and thus the no. 4

Detailed explanation Caterpillars and Leaves

public static int findUneatenLeaves(int[] array, int n) {
ArrayList<Integer> uneatenLeaves = new ArrayList<Integer>();
ArrayList<Integer> eatenLeaves = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
}
// 1. find the multiple of the eatenLeaves
for (int i = 0; i < array.length; i++) {
for (int j = 1; j < uneatenLeaves.size(); j++) {
if (array[i] * uneatenLeaves.get(j) <= n) {
}
}
}
for (int i = 0; i < eatenLeaves.size(); i++) {
for (int j = 1; j < uneatenLeaves.size(); j++) {
if (eatenLeaves.get(i) == uneatenLeaves.get(j)) {
uneatenLeaves.remove(uneatenLeaves.get(j));
}
}
}
System.out.println(uneatenLeaves.size());
return uneatenLeaves.size();
}


How can this be optimized?

• this sounds very similar to the sieve of eratosthenes, to which a number of well known optimizations exist. Have you taken a look at these? Commented Jun 29, 2015 at 21:42
• In particular, a Sieve of Eratosthenes looks like an optimization of this. Commented Jun 29, 2015 at 21:46
• K<15. So you can solve this way quicker using inclusion-exclusion principle in O(2^K) time and space, rather than going for the O(NK) version you have. Commented Aug 5, 2015 at 15:48
• I think you don't want to have a eatenLeaves array instead of that you can check mod of the uneatenLeaves array values with caterpillar number. For example: if(uneatenLeaves.get(j) % array.get(i) == 0){uneatenLeaves.remove(uneatenLeaves.get(j));} Commented Jan 20, 2019 at 18:13

# Best practices:

So I'll just shortly go through some of the basic beginner mistakes and best-practice "violations" I encounter around here, and tell you how well you did :)

### Formatting:

On this front that's an awesome job, well done

### Abstraction:

The code's a little lacking in that respect. The general goal in Java is to program against interfaces. This means:

ArrayList<Integer> uneatenLeaves = new ArrayList<Integer>();


becomes (after applying the Diamond Operator)

List<Integer> uneatenLeaves = new ArrayList<>();


### Naming:

Naming is one of the hardest things to get right when coding. It's extremely important to have names speaking for themselves, variables containing "exactly what it says on the tin".
This allows to grasp the meaning of code much quicker.

array and n aren't really good names. If I understand the code correctly, jumpNumbers and limit would be better names.

# Actual code-review

As already mentioned in a comment, this problem seems to be a variation of the Sieve of Eratosthenes, which is used for finding prime numbers.
Can you see the parallels yet?

To make it simple, you want a way to model two states. The better choice than a number (going from roundabout -2.150.000 to 2.150.000) is a boolean, which is either true or false.

Now we also know how often that state needs to be modeled, each leaf gets a separate boolean. If we pass the leaf with a caterpillar it gets eaten, and is no more there. The simplest way to model that is setting the symbolizing boolean to false.

Another interesting construct here is the do-while loop. A caterpillar eats the next leaf, if (and only if) the next leaf exists. The next leaf is calculated by $A_j * increment$ or even $current + A_j$. In combination with the number of leaves this makes a nice "terminating condition":

while (nextLeaf < leaves.size)


now we just do that for each caterpillar and suddenly we end up at following pseudocode:

// leaf 0 has already been eaten, since caterpillars always start there
foreach (jump_size in jump_numbers) {
current = 0;
while (next_leaf < leaf_count) {
current = current + jump_size;
eat current;
}
}


Implementing this into actual code is left as an exercise to the reader ;)

The complexity can't be of $O(N)$ or even $O(N/K)$. My algorithm is of $O(2^K)$, which is huge in itself but still acceptable. Even if I pass N = Long.MAX_VALUE, I get immediate results. Though if K is greater, the code may take time or the code may break when LCM of all jump values exceeds Long.MAX_VALUE.

To explain it, let's take A = {4, 5, 6} and N = 20.

We can count uneaten leaves are {1, 2, 3, 7, 9, 11, 13, 14, 17, 19} = 10

How can we get this result without counting?

N - (N / 4) - (N / 5) - (N / 6) + (N / 20) + (N / 12) + (N / 30) - N / 60
= 20 - 5 - 4 - 3 + 1 + 1 + 0 - 0 = 20 - 12 + 2 = 10


Caterpillar Uneaten Leaves Problem

• Welcome to Code Review! A link to a solution is welcome, but please ensure your answer is useful without it: add context around the link so your fellow users will have some idea what it is and why it’s there, then quote the most relevant part of the page you're linking to in case the target page is unavailable. Answers that are little more than a link may be deleted. Commented Aug 23, 2018 at 20:47