Google fulltime 电面

hesha0987 发表于 2016-2-26 02:13
我目前想到的是：
要减去的部分是：集合里面每个数进行等比数列求和
最后要加上的部分是：集合里面的数 ...

你把他看成how many subsets in a set with k elements就是2^k了。准确的说是Θ((2^k)-k), 也就是O(2^k)

补充内容 (2016-2-26 06:41):
我可能描述得不好， 把你confused了。

主要的步骤就是
1. 1...n求和 (sum)
2. 遍历x所有子集，空集和1个元素的子集除外
   2.1 求出每个子集的所有元素的product
   2.2 从sum里减掉该product和他的倍数

补充内容 (2016-2-26 06:52):
=_=|| 步骤是错的。请忽略

song4you 发表于 2016-2-26 06:05
你把他看成how many subsets in a set with k elements就是2^k了。准确的说是Θ((2^k)-k), 也就是O(2^k)
...

楼主真聪明啊！顿悟了。。那我想的那个公式化简之后应该就是2^k吧。。。。 数学差真心塞。。

song4you 发表于 2016-2-26 06:05
你把他看成how many subsets in a set with k elements就是2^k了。准确的说是Θ((2^k)-k), 也就是O(2^k)
...

要除开只有一个元素的子集？那如果x={2,3}, 子集{2}就不算在里面了？也不对啊

补充内容 (2016-2-26 07:51):
子集{2},{3}都没有了,集合本身算不算子集呢？如{2,3}

ohuohuo 发表于 2016-2-26 07:49
要除开只有一个元素的子集？那如果x={2,3}, 子集{2}就不算在里面了？也不对啊

补充内容 (2016-2-26 07:5 ...

恩啊。 算的。 除空集和单元素子集， 都算。 空集不用说了， 单元素子集是因为之前减掉了，所以不用继续考虑。

hesha0987 发表于 2016-2-26 07:25
楼主真聪明啊！顿悟了。。那我想的那个公式化简之后应该就是2^k吧。。。。 数学差真心塞。。

我数学也好差。。我现在半天也还是推不出他给我的solution的general公式。 ╮(╯_╰)╭

stefan0428 发表于 2016-2-25 14:32
可不可以先求出总和 然后根据X 求出小于N的所有丑数， 然后在减掉

丑数是只能被2,3,5整除吧。 x里可以是任意质数，7,11,13,17...都可以。 只减丑数的话会漏掉很多吧

zddllc 发表于 2016-2-26 04:35
感觉就是leetcode的 super ugly number.
求出小于n的super ugly number, 然后求和的时候不考虑这些ugly nu ...

我看了下leetcode上的解法，好像最快是O(n*lgk)？ 在这题给的条件1 < N <= 2^31; 1 <= K = X.size() <= 10里， 当n>10,000; k>1 的时候，O(n*lgk)还是要比O(2^k)慢

ohuohuo 发表于 2016-2-26 07:49
要除开只有一个元素的子集？那如果x={2,3}, 子集{2}就不算在里面了？也不对啊

补充内容 (2016-2-26 07:5 ...

他只给我推演了k=3的公式:

sum = n*(n+1)/2

Sum of prime multipliers:
primeSum1 = x[0] * (m*(m+1)/2) where m = n / x[0]
primeSum2 = x[1] * (m*(m+1)/2) where m = n / x[1]
primeSum3 = x[2] * (m*(m+1)/2) where m = n / x[2]
primeSum = primeSum1 + primeSum2+primeSum3

sum of repeatedly removed Multipliers
p1 = x[0]*x[1] * (m*(m+1)/2) where m = n / p
p2 = x[0]*x[2] * (m*(m+1)/2) where m = n / p
p3 = x[1]*x[2] * (m*(m+1)/2) where m = n / p
p = p1 + p2 + p3   (exclude the one greater than n)

commonMultiplier = (x[0]*x[1]*x[2])* (m*(m+1)/2) where m = n / commonMultiplier

Result:
sum = sum - primeSum + p - commonMultiplier

我也不知道为什么最后要减掉三个数的乘积， 但是这个公式在k=3的时候结果是对的。k>3的时候会有问题，这个公式应该有个general form。 不知道有没有大神能推出来。我推出来的公式只在k<6的时候正确。。o(╯□╰)o

这是数学题啊。。。
就是totalsum - 有一个1prime的那些数的sum + 有两个primes的数的sum - 有3个primes的数的sum + 有4个primes 数的sum。。。。。。一直到k个primes的数

主要就是combination(k, i), i=1,..k

啊，这题做电面太凶残了。。。。

echo33 发表于 2016-2-27 03:03
这是数学题啊。。。
就是totalsum - 有一个1prime的那些数的sum + 有两个primes的数的sum - 有3个primes的 ...

我去。 膜拜大神！！我按你的公式写出来了! 我试了下worst case， 这个公式秒出答案， kn等了好几分钟。。我果然数学太渣了。。。