由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求教EA一道面试题
相关主题
问一道 Interviewstreet 上的题 (JAVA)请教一道题的算法!! (转载)
面试题求解求两个或N个数的最大公约数和最小公倍数
贡献个面试题,目前狗狗都没找到.....Apple 面经
Interview street上的一题求助求教一个智力题
我的B2B面试 - 2 (没有多少技术题)求教一道最大公约数的题
谁能给个小于n^3的算法问一道电面题
brainteaserUber前途已尽(包括中国克隆版滴滴快的)
不用大整数如何计算组合数?三国贾诩“跳槽”经验多 信誉度和忠诚度没有受到怀疑 (转载)
相关话题的讨论汇总
话题: long话题: it1话题: int话题: it2话题: numbers
进入JobHunting版参与讨论
1 (共1页)
s******i
发帖数: 236
1
https://www.hackerrank.com/challenges/unfriendly-numbers
There is one friendly number and N unfriendly numbers. We want to find how
many numbers are there which exactly divide the friendly number, but does
not divide any of the unfriendly numbers.
Input Format:
The first line of input contains two numbers N and K seperated by spaces. N
is the number of unfriendly numbers, K is the friendly number.
The second line of input contains N space separated unfriendly numbers.
Output Format:
Output the answer in a single line.
Constraints:
1 <= N <= 10^6
1 <= K <= 10^13
1 <= unfriendly numbers <= 10^18
Sample Input:
8 16
2 5 7 4 3 8 3 18
Sample Output:
1
后面几个case很大,常规解法timeout
我的解法是把数组里每个数跟K的最大公约数放进set1,然后再生成K的所有因数set2,
如果set1里的数能整除set2里的一个数,就把它erase。return set1的size。代码如下:
int unfriendlyNumbers(vector < long long int > a,long long int k) {
int ans;
ans = 0;
set < long long int > divisors;
for(long long int i = 1; i<=sqrt(k); i++){
if(k%i == 0){
divisors.insert(i);
divisors.insert(k/i);
}
}
set < long long int > GCDs;
for(long long int j = 0; j GCDs.insert(GCD(a[j],k));
}
set < long long int > ::iterator it1,it2;
for(it1=GCDs.begin();it1!=GCDs.end();it1++){
for(it2=divisors.begin();it2!=divisors.end();it2++){
if((*it1)%(*it2)==0) divisors.erase(*it1);
}
}
ans = divisors.size();
return ans;
}
问题使我提交之后不能通过所有case。求板上大神指点。
s**********r
发帖数: 8153
2
这是啥面试啊?
l*********8
发帖数: 4642
3
倒数第6行:
divisors.erase(*it1) 改成
divisors.erase(*it2)
就行了。
我试过了,可以通过。

N

【在 s******i 的大作中提到】
: https://www.hackerrank.com/challenges/unfriendly-numbers
: There is one friendly number and N unfriendly numbers. We want to find how
: many numbers are there which exactly divide the friendly number, but does
: not divide any of the unfriendly numbers.
: Input Format:
: The first line of input contains two numbers N and K seperated by spaces. N
: is the number of unfriendly numbers, K is the friendly number.
: The second line of input contains N space separated unfriendly numbers.
: Output Format:
: Output the answer in a single line.

y***n
发帖数: 1594
4
仔细看了这个网站,印度人开的,还不错。有时间试一试。。
1 (共1页)
进入JobHunting版参与讨论
相关主题
三国贾诩“跳槽”经验多 信誉度和忠诚度没有受到怀疑 (转载)我的B2B面试 - 2 (没有多少技术题)
【报Offer】领英和某S谁能给个小于n^3的算法
求助 google 一道coding题brainteaser
Water and Jug Problem面试的时候给哪个答案好不用大整数如何计算组合数?
问一道 Interviewstreet 上的题 (JAVA)请教一道题的算法!! (转载)
面试题求解求两个或N个数的最大公约数和最小公倍数
贡献个面试题,目前狗狗都没找到.....Apple 面经
Interview street上的一题求助求教一个智力题
相关话题的讨论汇总
话题: long话题: it1话题: int话题: it2话题: numbers