Caterpillar uneaten leaves

Question

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++) {
        uneatenLeaves.add(i);
    }
    // 1. find the multiple of the eatenLeaves
    for (int i = 0; i < array.length; i++) {
        eatenLeaves.add(array[i]);
        for (int j = 1; j < uneatenLeaves.size(); j++) {
            if (array[i] * uneatenLeaves.get(j) <= n) {
                eatenLeaves.add(array[i] * uneatenLeaves.get(j));
            }
        }
    }
    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?

Answer 1

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

Answer 2

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