毛毛虫和叶子.我们能做得比O(n*c)好吗？

Question

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

假设一些毛毛虫从底部开始并跳到下一片叶子.他们在跳到下一个之前吃了叶子.我们得到一个数组,代表毛毛虫的跳跃步骤.如果阵列是[2,4,7],这意味着卡特彼勒[0]将吃叶2,4,6 ..卡特彼勒[1]会吃叶4,8,12 ..而卡特彼勒[2]会吃7 ,14,21 ...... 0代表地面.计算未吃叶子的数量.

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

设c为毛毛虫的数量,n为叶子的数量.

显而易见的蛮力解决方案是针对每个毛毛虫在大小为n的布尔阵列上进行迭代,如果吃掉则将其标记为真,否则将其标记为假.它需要O(n*c)时间.我们可以做得更好吗？

Answer 1

毛毛虫吃了它的所有"跳跃步骤" j,因此如果它是单独的,每只毛毛虫都会吃掉floor(n/j)叶子.

现在你必须弄清楚你已经多次计算了哪些叶子.例如,如果您计算第一条毛毛虫可以分割2的所有叶子,那么您不必计算第二条毛虫的任何叶子,第二条毛毛虫以4比4的速度跳跃.

对于两个项目,这些计数两次的数字是两个项目的最小公倍数的倍数,并且有floor(n/lcm(j,j'))这些项目.

请注意,对于三个术语,如果执行此计算,则可能会删除一些项目两次:让我们在您的示例中取28.它将被毛毛虫用跳跃步骤7吃掉,但是对其他人来说都是吃掉的(因为28%4 = = 28%2 == 0),因此你需要添加多次被删除的倍数:floor(n/lcm(j,j',j"))

你可以在这里看到一个模式,它是包含 - 排除原则.通用公式如下:

让Aj成为毛毛虫吃的叶子,跳跃步骤j(如果它是单独的).然后,对于J,一组几个capterpillar跳跃集,A _J是所有这些毛虫吃掉的一组叶子.

让我们将一个集合的最小公倍数定义为集合中所有元素的最小公倍数,因此我们可以编写lcm(J).

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

你现在有2个^c项的总和*,因为这是c毛毛虫的子集数量.请注意,您可以通过保存最不常见的倍数来节省一些时间,而不是从头开始重新计算它们.

我留下将实际代码写成"作为练习",正如一些人喜欢说的那样:它基本上迭代子集并计算最小公倍数,然后将它们全部放在上面的总和中.

这可以获得吃掉叶子的总数.从这里获得未吃的人是微不足道的.

如果我们在一个小例子(能够检查)上做,地面,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大1cm.你可以停止迭代.