痘印面经

抖音面经：

给一个数组A，例如[4,6,7]. 一个操作指的是 你可以选择任意一个数，使其增加1。
问至少需要多少个操作，能让该数组的最大公约数gcd大于1。例如可以使7增加1变成8，则原

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

还在讨论这道题，直接挂断，离面试结束还有15分钟呢。

抛砖引玉一下：

key observation: 假设数组A的最少值和奇数元素的个数分别为a和m，那么最多需要m次操作让该数组的gcd大于1，即把所有的奇数加一（全偶数），gcd最少为2

接下来考虑可能的GCD的search space：
1） 无需考虑大于或等于a+m的gcd，因为它们需要的操作一定比全偶数一样或更差
2） 在剩余的search space [2, a+m-1] 中无需考虑非质数：假设非质数z = x * y，能被z整除的整数集合为Z，能被x整除的整数集合为X，能被y整除的整数集合为Y，那么Z一定分别时X和Y的子集，换句话说，A中一个数字想要成为Z的元素，需要的操作要比成为X或Y中的元素一样或更多。

可以通过 质数筛算法找到[2, a+m-1] 中的所有质数作为gcd的candidate，分别求需要多少操作，然后最终选择最小的，最终复杂度为n *（a+m) * log log(a+m)  其中 n 是数组长度，m是数组中奇数的个数，a是数组的最小值

着实不做人，光背GCD的loop写法就够恶心人了。

这人提前挂了 刚好和HR申诉要加面啊

619899442 发表于 2023-9-20 23:30
抛砖引玉一下：

key observation: 假设数组A的最少值和奇数元素的个数分别为a和m，那么最多需要m次操作 ...

不懂为啥要a+m，明明m就是最大了呀~所有奇数变偶数就是search space的上限了吧……

hels 发表于 2023-9-21 08:10
不懂为啥要a+m，明明m就是最大了呀~所有奇数变偶数就是search space的上限了吧……

这里的search space指的是GCD的search space，比如lz的例子 [6,7,7,7] ，这里a=6, m=3, 最优GCD的upper bound是6+3 = 9，因为更大的GCD已经需要比3（全偶数次操作）更多次操作用在最小元素上了

还有15分钟就挂，太坑了吧

619899442 发表于 2023-9-21 00:30
抛砖引玉一下：

key observation: 假设数组A的最少值和奇数元素的个数分别为a和m，那么最多需要m次操作 ...

兄弟第二个constraint你是怎么approach的啊，我第一个constraint是秒想，但是第二个感觉还有考验数学的思维和反映了

补充内容 (2023-09-23 07:26 +08:00):

当然也有可能我刷题太少了哈哈哈哈

小亩_psg90s6 发表于 2023-9-22 16:24
兄弟第二个constraint你是怎么approach的啊，我第一个constraint是秒想，但是第二个感觉还有考验数学的思 ...

哈哈😬 我觉得第二个只是个锦上添花的optimization，看了你的回复我才意识到到前面的复杂度错了，有constraint2 optimization的话是 n * (a + m) / log(a + m) + (a + m) * loglog(a+m), 没有那个optimization的话是 n * (a + m)，其实没有差那么多的