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

• 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 uneatenLeaves = new ArrayList();
ArrayList eatenLeaves = new ArrayList();
for (int i = 1; i

How can this be optimized?

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 uneatenLeaves = new ArrayList();

becomes (after applying the Diamond Operator)

List 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 ;)

StackExchange Code Review Q#95145, answer score: 5