给定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等于6

一个完美的整数。 但是对于N = 12

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非常大,您可以使用二进制搜索。