网易笔试，求最大奇约数和，O(n)复杂度超时
有跑出来的吗，我用python时间超了。
还是直接公式推出来的。
2016-09-12 21:10 成都信息工程大学 Java
关注
全部评论
LocksonJu
影石创新科技股份有限公司_视觉算法工程师
long long findSum(int N)
{
if (N == 1)
return 1;
long long k = (N + 1) / 2;
return k*k + findSum(N / 2);
}
神公式
DoubleEgg_Liu
华中科技大学 C++
int main() {
int n; cin >> n;
long long sum = 0;
int t;
for (int i = 1; i <= n; i += 2) {
t = i;
while (t <= n) { t *= 2; sum += i;}
}
cout << sum;
}
糖糖不爱吃糖
哈尔滨工程大学 Java
考试后，和学弟们讨论得出了答案，logn的，也去网易的笔试题真题哪里测试了下，通过了，虽然笔试中没有做出来，不过后来没有看别人的现成的答案，而是我们集思广益想出来的，还是蛮开心的，这也是笔试的收获吧
JUST&GO
四川大学 C++
怎么说呢。我觉得其实有规律的。
每4个看成一组。
不过最近一直没去解。。当时考试考到最后几分钟才反映过来。
牛客300474号
西南交通大学 运维工程师
位运算可以 res = n / (n & -n) 得到最大奇数
牛客11111111
东南大学 C++
#include <iostream>
using namespace std;
int main()
{
long n;
cin>>n;
long long res=0;
long t=2;//用t表示2^k
int count=0;
while(count<n/2)
{
for(long i=1;t*i<=n;i=i+2)//找到2^k*i<=n的所有i
{
res=res+i;
count++;
}
t=t*2;
}
if(n%2==0) //当n为奇数时，序列中的奇数和
{
res=res+n*n/4;
}
else//当n为偶数时，序列中的奇数和
{
res=res+(n+1)*(n+1)/4;
}
cout<<res<<endl;
return 0;
}
菜豆
上海大学 测试工程师
用移位操作做除2操作就可以不超时
牛客615963号
国际关系学院 C++
推公式推了半天, 只能O(1)的解决一半, 剩下的一半推死推不出来.
比如对于100的话能直接算出1-64的和 , 最后没办法只好遍历了. 没想到过了.
寒武纪三叶草
开始用python一直超时，换C++才AC了
董泽锋
西南交通大学 C++
unsigned long long cal(unsigned long long n){
unsigned long long sum = 0;
do
{
if (n % 2 == 0) {
sum += (long long)(n/2)*(n / 2);
n = n / 2;
} else {
sum += n;
n = n - 1;
}
} while (n != 1);
return sum + 1;
}
Small_White
湖南工业大学 运维工程师
超时 ，好伤心。
冰月冷望 楼主
楼主 成都信息工程大学 Java
哎，O(logN)
94sd
北京科技大学 算法工程师
一直除以2超时，改成移位运算超时，我真不知道怎么做了，与网易无缘了，😭
luohan
北京林业大学 算法工程师
都100亿了，O(N)肯定超时啊。O(N)在1s内也就解1亿左右的数据了，常数还不能太大
紫荆的传说
北京大学 测试工程师
C++超时……
Riosngdfleiw1965
中央音乐学院 PHP
最大奇约数，奇数就是本身，偶数/2直到奇数为止，但还是不行，始终要循环
之乎者也
东南大学 C++
最后想起来的，妈的交卷了，坑爹啊
项煜东
中国科学技术大学 C++
每个奇数*2*2*2。。。
子「月」乐
西安邮电大学 Java
在交卷的一瞬间，我知道我超时的原因了，一直除以二就可以解决问题，再次GG
山野闲居
西安电子科大 C++
看了讨论区logn的答案，真是觉得生无可恋了
相关推荐
不愿透露姓名的神秘牛友
昨天 11:32
点赞 评论 收藏
分享
点赞 评论 收藏
分享
HeaoDng：美团好像可以触发一面通
点赞 评论 收藏
分享
10-19 15:33
蚌埠坦克学院 算法工程师 点赞 评论 收藏
分享
美的集团公司福利 783人发布