给定n,找到为n得到的最大数字
问题在oracle面试中提出。例如,如果我的输入是6,那么
- 5 + 1 = 6答案:2
- 4 + 2 = 6答案:2
- 3 + 2 + 1 = 6答案:3
所以,最终答案应该是3.(即获得总和6需要3,2,1)
注意 :不允许重复数字(即1 + 1 + 1 + 1 + 1 + 1 = 6)
我用递归解决了它,但面试官并不满意。 动态编程是否可行?
我准备发布答案,但@Cruise Liu打败了我。 我试着解释一下。 它是一种整数分区,但你不需要生成元素,因为你只对’元素数’感兴趣。 即最终答案3而不是{1,2,3}
给定数字N,您有另一个限制,数字不能重复。 因此,最好的情况是如果N实际上是一个数字,例如1,3,6,10,15
ie f(x) = x * (x + 1) / 2.
例如,取6. f(x)= 6存在。 特别是f(3)= 6。 这样你就得到了答案3。
这意味着如果存在f(x)= N的整数X,那么有一组数字1,2,3 …… x在加起来时给出N.这是最大数可能(没有重复)。
但是,有些情况在f(x)= N,其中x不是整数。
f(x) = x * (x + 1 ) / 2 = N ie x**2 + x = 2*N x**2 + x - 2*N = 0
我们得到了解这个二次方程式
由于数字x不是负数,我们不能拥有
所以我们离开了
对于N = 6
一个完美的整数。 但是对于N = 12
这是8.845 / 2这是一个分数。 楼层值为4,这就是答案。
简而言之:实现函数f(N)=(int)((-1.0 + sqrt(1 + 8 * N))/ 2.0)
即
int max_partition_length(int n){ return (int)((-1.0 + sqrt(1 + n*8))/2); }
x数的最小总和是
所以只需找到满足不等式的x:
这是代码:
#include int main() { int n; scanf("%d", &n); int x = 1; while ((x+1)*x/2 <= n) x++; x--; // now (x+1)*x/2 > n , so x is too large printf("%d\n", x); return 0; }
如果n非常大,您可以使用二进制搜索。