编写程序求满足1+2+3+4+…+n>=10000 的最小的正整数n为多少。
看到这个题目感觉有点意思,O(n)的解法容易实现,已经有其它答案写了就不再重复了。下面是用“二分查找”思想写的时间复杂度为O(log(n))的解法,仅供参考。自测输入10000的话答案是141.
public class MinN {
public static void main(String[] args) {
int target = 10000; //目标值
int ans = findN(target);
System.out.println(ans);
}
/**
* 二分查找
* */
public static int findN(int target) {
int i = 1,j = target;
while (i <= j) {
int mid = (i + j) / 2;
long tmp = sum(1,mid);
if(tmp >= target) {
if(sum(1,mid) < target) {
return mid;
} else {
j = mid - 1;
}
} else {
i = mid + 1;
}
}
return i;
}
/**
* 求从start加到end的和。使用long类型避免计算后超出整数范围
* */
public static long sum(int start,int end) {
return (long) (end - start + 1) * (long) (start + end) / 2;
}
}
提供一个大致思路供参考,复杂度O(1)。
推公式,解方程,判断情况,结果向上取整。
n * (n + 1) / 2 = 10000
public class Main {
public static void main(String[] args) {
int sum = 0, n = 0;
while(true) {
sum += ++n;
if(sum > 10000) {
break;
}
}
System.out.println(n);
}
}