algorithm - 毛毛虫和叶子。我们可以做得比O(n * c)好吗？

Question

在准备面试时发现了这个问题。

假设一些毛毛虫从底部开始，然后跳到下一个叶子。他们
在跳到下一个之前先吃掉叶子。我们得到了一个代表跳跃步骤的数组
由毛毛虫制成。如果数组为[2,4,7]，则意味着毛毛虫[0]将吞食叶子2、4、6。
caterpillar [1]将吃掉叶子4,8,12 ..，而caterpillar [2]将吃掉7,14,21 ... 0代表地面。
计算未食用叶子的数量。

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

令c为毛毛虫的数量，n为叶片的数量。

明显的蛮力解决方案是遍历每个毛虫的n个 bool 数组，并将其标记为true(如果食用)，否则标记为false。这需要O(n * c)时间。我们可以做得更好吗？

Answer 1

一条毛毛虫会吃掉其“跳跃步骤” j的所有倍数，因此，如果单独一个，每个毛毛虫都会吃floor(n/j)叶子。

现在，您必须弄清楚数了数次。例如，如果您为第一个毛毛虫算出所有可被2整除的叶子，那么您就不必为第二个毛毛虫算出任何叶子，第二个毛毛虫跳4乘4。

对于两个项目，计算两次的这些数字是两个项目的least common multiple的倍数，并且存在这些项目的floor(n/lcm(j,j'))。

请注意，对于这三个术语，如果执行此计算，则可能会删除两次某些项:在我们的示例中，我们取28。毛毛虫将在第7步中将其吃掉，但会同时计数(因为28％4 == 28％2 == 0)，因此您需要添加多次删除的倍数:floor(n/lcm(j,j',j"))
您可以在这里看到一个模式，它是the inclusion-exclusion principle。通用公式如下:

令Aj为毛虫吃掉的叶子，跳步为j(如果是单独的话)。然后，对于J来说，是一组由几个毛毛虫组成的跳跃集，AJ是所有这些毛毛虫吃掉的叶子。

让我们还将集合的最小公倍数定义为集合中所有元素的最小公倍数，以便我们可以编写lcm(J)。

包含-排除公式中的[n]是所考虑的毛毛虫跳跃的集合，因此，在您的情况下为[2,4,7]，我们对它的所有子集进行迭代。 |J|是子集的大小，| AJ |是J中每个毛毛虫可以吃的叶子数的大小，所以我们得到| AJ |。 = floor(n/lcm(J))。

现在，您拥有2c项的总和*，因为这是c毛毛虫的子集的数量。请注意，您可以节省一些时间，方法是保存最小公倍数，而不用从头开始重新计算它们。

就像有人说的那样，我将实际代码写为“作为练习”:它基本上是在子集上迭代并计算最小公倍数，然后将它们全部放在一起。

这可以让您获得被食用的叶子的总数。从这里得到未吃的东西是微不足道的。

如果我们在一个小示例(可以检查)上进行操作，则地面为0，对叶子进行1..24，对毛毛虫的跳跃步骤进行[2,3,4]。

唯一幸存的叶子将是{1、5、7、11、13、17、19、23}:删除所有偶数和可除以3的所有数字。也就是说，我们希望答案是8。

第一轮:大小为1的子集。

毛毛虫j=2会单独吃24/2 = 12片叶子

毛毛虫的j=3会单独吃24/3 = 8片叶子

毛毛虫j=4会单独吃24/4 = 6片叶子

第二轮:大小为2的子集。

卡特彼勒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定位

第三轮:大小为3的子集:所有毛毛虫在一起

他们都想吃24/lcm(2,3,4)= 24/12 = 2片叶子:{12，24}。

最后一轮:12 + 8 + 6-4-2-6 + 2 = 26-12 + 2 = 16被吃掉的叶子

因此，剩下的24-16 = 8片叶子。

*当然，这是最坏的情况。希望您会遍历大小递增的子集，并且一旦子集J的最小公倍数大于n，您就可以忽略该J的所有超集。特别是，如果大小k的所有子集都具有lcm大于n，则可以停止迭代。