algorithm - Caterpillars and Leaves. Can we do better than O(n*c)? -

found question while preparing interviews.

suppose caterpillars start bottom , jump next leaf. eat leaf before jumping next. given array represents jump steps made caterpillars. if array [2,4,7], means caterpillar[­0] eat leaf 2,4,6.. caterpillar[­1] eat leaf 4,8,12.. , caterpillar­[2] eat 7,14,21...0 represents ground. calculate number of uneaten leaves.

let assume caterpillar jumps next destination if current leaf eaten. means, if caterpillar[7] finds leaf 28 eaten, proceed eat leaf 35.

let c number of caterpillars , n number of leaves.

the obvious brute force solution iterating on bool array of size n each caterpillar , mark true if eaten or false otherwise. takes o(n*c) time. can better?

a caterpillar eats multiple of 'jump step' j, if alone, each caterpillar eat floor(n/j) leaves.

now have got figure out leaves have counted several times. example if count leaves dividable 2 first caterpillar, don't have count leaves second caterpillar, jumps 4 4.

for 2 items, these numbers counted twice multiples of least common multiple of both items, , there floor(n/lcm(j,j')) of those.

note 3 terms, if computation, might remove items twice : let take 28 in example. eaten caterpillar jump step 7, counted both others (because 28 % 4 == 28 % 2 == 0), need add multiples removed multiple times : floor(n/lcm(j,j',j"))

you can see pattern here, it's the inclusion-exclusion principle. general formula follows :

let aj leaves eaten caterpillar jump step j (if alone). j set of several capterpillar jump sets, a_j set of leaves eaten of these caterpillars.

let define least common multiple of set least common multiple of elements in set, can write lcm(j).

the [n] in inclusion-exclusion formula set of considered caterpillar jumps, in case [2,4,7], , iterate on subsets of it. |j| size of subset, , |a_j| size of number of leaves each caterpillar in j eat, |a_j| = floor(n/lcm(j)).

you have sum of 2^c terms *, since numbers of subsets of c caterpillars. note can save time saving least common multiples instead of recomputing them scratch.

i leave writing actual code "as exercise", : iterating on subsets , computing least common multiples, putting in sum above.

this gets total number of eaten leaves. getting uneaten ones here trivial.

---

if on small example (to able check), 0 ground, 1..24 leaves, , [2,3,4] caterpillar jump steps.

the surviving leaves {1, 5, 7, 11, 13, 17, 19, 23} : removing numbers , numbers dividable 3. is, expect answer 8.

• first round : subsets of size 1.
  • caterpillar j=2 would, alone, eat 24/2 = 12 leaves
  • caterpillar j=3 would, alone, eat 24/3 = 8 leaves
  • caterpillar j=4 would, alone, eat 24/4 = 6 leaves
• second round : subsets of size 2.
  • caterpillar j=2 , j=3 both eat 24/6 = 4 leaves : {6, 12, 18, 24}
  • caterpillar j=3 , j=4 both eat 24/12 = 2 leaves : {12, 24}
  • caterpillar j=4 , j=2 both eat 24/4 = 6 leaves : eaten 4 targeted 2
• third round : subsets of size 3 : caterpillars
  • they eat 24/lcm(2,3,4) = 24/12 = 2 leaves : {12, 24}.
• final round : 12 + 8 + 6 - 4 - 2 - 6 + 2 = 26 - 12 + 2 = 16 leaves eaten

so 24 - 16 = 8 leaves remain.

---

* of course worst case scenario. iterate on subsets of increasing sizes, , least common multiple of subset j bigger n, can disregard supersets of j. in particular, if subsets of size k have lcm bigger n, can stop iterating.