Caterpillars and leaves. Can we do better than O (n * c)?

Question

Found this question in preparation for the interview.

Suppose some tracks start at the bottom and move on to the next sheet. They eat the leaf before jumping to the next. We are given an array that represents the transition steps made by the caterpillars. If the array is [2,4,7], this means that the caterpillar [0] will eat the leaf 2,4,6 .. the caterpillar [1] will eat the leaf 4,8,12 .. and the caterpillar [2] will eat 7 , 14.21 ... 0 represents the earth. Calculate the number of unbound leaves.

Suppose the caterpillar moves to the next destination if the current leaf is eaten. This means that if the caterpillar [7] finds that leaf 28 is eaten, it will continue to eat leaf 35.

Let c be the number of tracks, n be the number of leaves.

An explicit brute force solution iterates over the bool array of size n for each caterpillar and marks it as true if it exists or is false otherwise. It takes O (n * c) time. Can we do better?

Answer 1

The caterpillar eats everything that is a multiple of its "transition step" j , so if it were alone, each caterpillar eats the leaves floor(n/j) .

Now you need to find out what you think several times. For example, if you count all leaves that can be divided by 2 for the first caterpillar, you do not need to count the leaves for the second caterpillar that jumps 4 to 4.

For two elements, these numbers, read twice, are multiples of the smallest total number of both elements, and there is floor(n/lcm(j,j')) of those.

Note that for the three terms, if you perform this calculation, you can delete several elements twice: take 28 in your example. It will be eaten by the caterpillar in 7 step steps, but it is considered for others (because 28% 4 == 28% 2 == 0), so you need to add multiples that have been deleted several times: floor(n/lcm(j,j',j"))

Here you can see the pattern, the principle of exclusion of inclusion . From here follows the general formula:

Let Aj be the leaves eaten by a caterpillar with a transition step j (if they were alone). Then for J there are many sets of caperpillar jumps, A _J is a set of leaves eaten by all these caterpillars.

Let's also define the smallest common multiple of a set as the smallest common multiple of all elements in a set, so we can write lcm(J) .

[n] in the inclusion exclusion formula is a set of considered [2,4,7] jumps, so in your case [2,4,7] , and we [2,4,7] over all its subsets. |J| is the size of the subset, and | A _j | is the size of the number of leaves that each caterpillar in J could eat, so we get | A _j | = floor(n/lcm(J)) .

Now you have a sum of 2 ^c terms *, since this is the number of subsets of c tracks. Note that you can save some time by preserving the least common factors, rather than reprogramming them from scratch.

I leave writing the actual code “as an exercise,” as some say: it basically iterates over the subsets and calculates the least common factors, and then sums it all together in the sum above.

This gives you the total amount of leaves eaten. Getting inedible here is trivial.

---

If we do this with a small example (to check), with 0 ground, 1..24 leaves and [2,3,4] caterpillar transition steps.

The only surviving leaves will be {1, 5, 7, 11, 13, 17, 19, 23}: deleting all even numbers and all numbers divisible by 3. That is, we expect the answer to be 8.

• Round one: subsets of size 1.
  • Caterpillar j=2 will, alone, have 24/2 = 12 leaves
  • Caterpillar j=3 will, alone, have 24/3 = 8 leaves
  • Caterpillar j=4 will, alone, have 24/4 = 6 leaves
• Round two: subsets of size 2.
  • Caterpillar j=2 and j=3 would like to eat 24/6 = 4 sheets: {6, 12, 18, 24}
  • Caterpillar j=3 and j=4 would like to eat 24/12 = 2 sheets: {12, 24}
  • Caterpillar j=4 and j=2 would like to eat 24/4 = 6 leaves: all those who eat 4 are aimed at 2
• Round three: subsets of size 3: all tracks together
  • All of them would like to eat 24 / lcm (2,3,4) = 24/12 = 2 sheets: {12, 24}.
• Final round: 12 + 8 + 6 - 4 - 2 - 6 + 2 = 26 - 12 + 2 = 16 leaves eat

Thus, there remain 24 - 16 = 8 leaves.

---

* Of course, this is the worst case scenario. We hope you iterate over the subsets of increasing sizes, and as soon as the smallest common multiple of the subset J is greater than n , you can ignore all the supersets of this J. In particular, if all the subsets of size k have lcm greater than n, you can stop the iteration.

Answer 2

This refers to the O (n * c) algo you mentioned. This is O (n logc) if you take a closer look.

The caterpillar eats everything that is a multiple of its "transition step" j, so if it were one, each caterpillar could eat a floor (n / j).

This complexity is limited: n + n / 2 + n / 3 + ... + n / c <= n log (c)

This will not make any difference, since c is small, but just indicates :)

Check this link to implement Cimbali Inclusion-Exception : find out Uneaten Leaves algorithm error

EDIT:. Proof that the harmonic series is bounded by log (s). We use inequality for the lower limit of integration.