r*****t
发帖数: 2051 | 1 N是一个很大的正整数——可能到10^15次方，
简单起见，不考虑溢出，或者假设用python
A 是一个array，里面存着一些正整数，up to 1000个
从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？
举个例子：
N = 10
A = [2,4,5]
那么返回4 (1,3,7,9满足条件)
我写的如下，但是面试官不满意，因为N很大的时候内存会溢出
def left(N = 10, A = [2,4,5]):
ones = [1 for i in xrange(N+1)]
ones[0] = 0
for inte in A:
if inte == 1:
return 0
for i in xrange(1,N/inte+1):
ones[i*inte] = 0
return sum(ones) | w******n
发帖数: 61 | 2 是不是可以先处理一下A？比如有2的时候4就没必要了 | h****t
发帖数: 69 | 3 如果N很大的话你可以先找1-10000有多少数不能被A中的任何一个数整除的，接着找
10001-20000。。。。 | h**********c
发帖数: 4120 | 4 我觉得
先处理A成B, for any b_i in B，it has no multiple in B
for any b_i in B
c_i = N div b_i
sigma_c = sigma_c + c_i
return N - sigma_c
【在 r*****t 的大作中提到】
: N是一个很大的正整数——可能到10^15次方，
: 简单起见，不考虑溢出，或者假设用python
: A 是一个array，里面存着一些正整数，up to 1000个
: 从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？
: 举个例子：
: N = 10
: A = [2,4,5]
: 那么返回4 (1,3,7,9满足条件)
: 我写的如下，但是面试官不满意，因为N很大的时候内存会溢出
: def left(N = 10, A = [2,4,5]):
| s******d
发帖数: 9806 | 5 how about there's one number = b[i]*b[j]? you will count it twice. The hard
part of this question is how to eliminate these duplicates...
【在 h**********c 的大作中提到】
: 我觉得
: 先处理A成B, for any b_i in B，it has no multiple in B
: for any b_i in B
: c_i = N div b_i
: sigma_c = sigma_c + c_i
: return N - sigma_c
| x*********3
发帖数: 1438 | 6 这个是不对的，比如Ａ［２，３］， Ｎ＝６，你的结果是１，但应该是２。因为６除
了两次。就算你在结果里把Ｎ／２＊３加到结果里，结果依然有问题。
我是没想到比较好的方法，有人有比较好的办法吗？
【在 h**********c 的大作中提到】
: 我觉得
: 先处理A成B, for any b_i in B，it has no multiple in B
: for any b_i in B
: c_i = N div b_i
: sigma_c = sigma_c + c_i
: return N - sigma_c
| h**********c
发帖数: 4120 | 7 yes, there is miss
TBD
hard
【在 s******d 的大作中提到】
: how about there's one number = b[i]*b[j]? you will count it twice. The hard
: part of this question is how to eliminate these duplicates...
| h**********c
发帖数: 4120 | 8 那用个search tree
把A 的element 按divisible 关系做成树
用树来漏1-N
space is A space
仅供参考，低调 | w*****d
发帖数: 105 | 9 Consider the simplest case: A={2}, then any odd number below N is OK, so the
result would be (N - N/2). Then consider A={2, 3}, any number below N that
is not mutiply of 2 or 3 is OK, so the result would be (N - N/2 - N/3 + N/6)
. Then consider A={2, 3, 5}, the result would be (N - N/2 - N/3 - N/5 + N/6
+ N/10 + N/15 - N/30).
So there is a general rule:
for A={a1, a2, ..., aN}, if ai is not dividable by aj for any i != j, then
we could:
1. for i from 1 to N, calc r1 = N - SUM(N/ai);
2. for i, j from 1 to N, i != j, calc r2 = r1 + SUM(N/(ai*aj));
3. for i, j, k from 1 to N, i != j != k, calc r3 = r2 - SUM(N/(ai*aj*ak));
...
until all numbers in A are chosen.
then the final rN is the result.
So for the problem, first we preprocess A to eliminate any multiplies in A.
For example, A={2, 4, 5}, we can eliminate 4 because it is a mutiply of 2
which is also in A. So A'={2, 5}, then we calc:
r1 = 10 - 10/2 - 10/5 = 10 - 5 - 2 = 3;
r2 = r1 + 10/10 = 3 + 1 = 4;
then the final result is 4. | t******5
发帖数: 30 | | h*********2
发帖数: 444 | 11 你怎么eliminate any multiples
2和4这种还好
4和6这种怎么做？ 求最大公约数？
the
that
6)
6
【在 w*****d 的大作中提到】
: Consider the simplest case: A={2}, then any odd number below N is OK, so the
: result would be (N - N/2). Then consider A={2, 3}, any number below N that
: is not mutiply of 2 or 3 is OK, so the result would be (N - N/2 - N/3 + N/6)
: . Then consider A={2, 3, 5}, the result would be (N - N/2 - N/3 - N/5 + N/6
: + N/10 + N/15 - N/30).
: So there is a general rule:
: for A={a1, a2, ..., aN}, if ai is not dividable by aj for any i != j, then
: we could:
: 1. for i from 1 to N, calc r1 = N - SUM(N/ai);
: 2. for i, j from 1 to N, i != j, calc r2 = r1 + SUM(N/(ai*aj));
| l******r
发帖数: 18699 | 12 用筛法
【在 r*****t 的大作中提到】
: N是一个很大的正整数——可能到10^15次方，
: 简单起见，不考虑溢出，或者假设用python
: A 是一个array，里面存着一些正整数，up to 1000个
: 从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？
: 举个例子：
: N = 10
: A = [2,4,5]
: 那么返回4 (1,3,7,9满足条件)
: 我写的如下，但是面试官不满意，因为N很大的时候内存会溢出
: def left(N = 10, A = [2,4,5]):
| w********m
发帖数: 1137 | |
|
