毛虫和树叶。我们可以做的比为O（n * C）更好吗？ [英] Caterpillars and Leaves. Can we do better than O(n*c)?

问题描述

发现了这个问题，而preparing采访。

Found this question while preparing for interviews.

假设一些毛毛虫从底部并跳转到下一个叶开始。他们 跳转到下一个前吃树叶。我们给它重新presents跳步阵列 毛虫进行。如果数组为[2,4,7]，这意味着毛毛虫[0]会吃叶子2,4,6 .. 毛毛虫[1]将吃树叶4,8,12 ..和毛毛虫[2]会吃7,14,21 ... 0重新presents地。 计算吃剩的叶子的数量。

Suppose that some caterpillars start from the bottom and jump to the next leaf. They eat the leaf before jumping to next. We are given an array which represents jump steps made by caterpillars. If the array is [2,4,7], it means caterpillar[­0] will eat leaf 2,4,6.. caterpillar[­1] will eat leaf 4,8,12.. and caterpillar­[2] will eat 7,14,21...0 represents ground. Calculate the number of uneaten leaves.

让我们假设毛虫跳转到其下一个目的地，如果当前叶吃掉。这意味着，如果毛虫[7]发现叶28被吃掉，它将继续吃叶35

Let us assume that the caterpillar jumps to its next destination if the current leaf is eaten. This means, that if caterpillar[7] finds that leaf 28 is eaten, it will proceed to eat leaf 35.

让c是幼虫数和n是叶数

Let c be the number of caterpillars and n be the number of leaves.

最明显的蛮力解决方案是遍历大小为n的布尔数组，每个毛毛虫，它为真，如果食用或否则为false标记。这需要为O（n * C）的时间。我们可以做的更好？

The obvious brute force solution is iterating over a bool array of size n for each caterpillar and mark it as true if eaten or false otherwise. It takes O(n*c) time. Can we do better?

感谢。

推荐答案

一个毛毛虫吃了跳步Ĵ，因此，如果它是独自一人，每一个都多毛毛虫会吃地板（N / J）树叶。

A caterpillar eats all multiple of its 'jump step' j, thus if it were alone, each caterpillar would eat floor(n/j) leaves.

现在你得弄清楚这让你已经算好几次。例如如果算上那些整除2，第卡特彼勒叶，那你就不必指望任何叶子第二毛毛虫，谁4跳4。

Now you have got to figure out which leaves you have counted several times. For example if you count all leaves that are dividable by 2 for the first caterpillar, then you don't have to count any leaves for the second caterpillar, who jumps 4 by 4.

有关的两个项目，计算这些数字的两倍都是最小公倍数两个项目，并有地板（N / LCM（J，J'））的那些。

For two items, these numbers counted twice are the multiples of the least common multiple of both items, and there are floor(n/lcm(j,j')) of those.

请注意，对于三个词，如果你这样做计算，你可能会两次删除一些项目：让我们看看28在你的榜样。它将通过与跳步7毛毛虫吃，但数为别人（因为28％4 == 28％2 == 0），因此你需要添加被删除多次的倍数：地板（N / LCM（J，J'，J））

Note that for three terms, if you do this computation, you might remove some items twice : let us take 28 in your example. It will be eaten by the caterpillar with jump step 7, but counted for both others (because 28 % 4 == 28 % 2 == 0), thus you need to add the multiples that were removed multiple times : floor(n/lcm(j,j',j"))

您可以在这里看到一个模式，它的的容斥原理。一般公式如下：

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

让AJ可以用跳跃步骤j毛毛虫吃树叶（如果是单独的）。那么对于J A组若干capterpillar跳组，A <子>Ĵ是叶集所有这些毛毛虫吃的。

Let Aj be the leaves eaten by a caterpillar with jump step j (if it were alone). Then for J a set of several capterpillar jump sets, A_J is the set of leaves eaten by all of these caterpillars.

让我们还定义了一组作为集合中的所有元素的最小公倍数的最小公倍数，所以我们可以写 LCM（J）。

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

在容斥公式[n]是theb集合考虑毛虫的跳跃，因此你的情况 [2,4,7] ，我们遍历在这一切的子集。 |百灵| 的子集的大小和| A <子>Ĵ |是叶子为J每个毛毛虫可以吃的数量的大小，所以我们得到| A <子>Ĵ | = 地板（N / LCM（J））。

The [n] in the inclusion-exclusion formula is theb the set of considered caterpillar jumps, thus in your case [2,4,7], and we iterate over all the subsets of it. |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)).

您现在有2 ^C *看一笔，因为这是的子集了C 毛毛虫的数量。请注意，您可以通过保存的最小公倍数，而不是从头开始重新计算他​​们节省一些时间。

You now have a sum of 2^c terms *, since that is the numbers of subsets of the c caterpillars. Note that you can save some time by saving the least common multiples instead of recomputing them from scratch.

我离开编写实际的code锻炼，如一些喜欢说：它基本上是迭代子集和计算最小公倍数，然后把他们放在一起在上面的总和

I leave writing the actual code "as exercise", as some like to say : it is basically iterating over subsets and computing least common multiples, then putting it all together in the sum above.

这让你吃树叶的总数。获取吃剩的人从这里实在是微不足道。

This gets you the total number of eaten leaves. Getting the uneaten ones from here is trivial.

如果我们做一个小的例子（要能检查），0地面， [1,24] 树叶，和 [2,3,4] 的毛毛虫跳跃的步骤。

If we do it on a small example (to be able to check), with 0 the ground, [1,24] the leaves, and [2,3,4] the caterpillar jump steps.

唯一幸存的叶子会发{1，5，7，11，13，17，19，23}：由3即删除所有偶数和所有数字可分，我们预计答案是8

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

• 第一轮：1大小的子集。
  • 卡特彼勒 J = 2 会，独自吃24/2 = 12叶
  • 卡特彼勒 J = 3 会，独自吃24/3 = 8叶
  • 卡特彼勒 J = 4 会，独自吃24/4 = 6叶
  • 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
    • 卡特彼勒 J = 2 和 J = 3 将都喜欢吃24/6 = 4叶：{ 6，12，18，24}
    • 卡特彼勒 J = 3 和 J = 4 将都喜欢吃24/12 = 2叶：{ 12，24}
    • 卡特彼勒 J = 4 和 J = 2 将都喜欢吃24/4 = 6叶：全部那些由 4 食用由 2 定位
    • Caterpillar j=2 and j=3 would both like to eat 24/6 = 4 leaves : {6, 12, 18, 24}
    • Caterpillar j=3 and j=4 would both like to eat 24/12 = 2 leaves : {12, 24}
    • Caterpillar j=4 and j=2 would both like to eat 24/4 = 6 leaves : all those eaten by 4 are targeted by 2
    • 他们都喜欢吃24 / LCM（2,3,4）= 24/12 = 2叶：{12，24}

    所以，24 - 16 = 8树叶

    So 24 - 16 = 8 leaves remain.

    *的当然，这是最坏的情况。希望你会遍历尺寸增加的子集，并尽快的一个子集的最小公倍数J是大于 N ，你可以忽略那J.在所有的超集特别是，如果大小 K 的所有子集有一个LCM大于N，你可以停止迭代。

    * of course this is a worst case scenario. Hopefully you will iterate over subsets of increasing sizes, and as soon as the least common multiple of a subset J is bigger than n, you can disregard all supersets of that J. In particular, if all the subsets of a size k have an lcm bigger than n, you can stop iterating.

    这篇关于毛虫和树叶。我们可以做的比为O（n * C）更好吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！