给定n,找到为n得到的最大数字

Question

问题在oracle访谈中提出.例如,如果我的输入是6,那么

• 5 + 1 = 6 Ans:2
• 4 + 2 = 6答案:2
• 3 + 2 + 1 = 6答案:3

所以,最终的答案应该是3.(即获得总和6需要3,2,1)

注意:不允许重复数字(即1 + 1 + 1 + 1 + 1 + 1 = 6)

我用递归解决了它但面试官并不满意.动态编程是否可行？

Answer 1

x数的最小总和是

所以只需找到满足不等式的x:

这是代码:

#include <stdio.h>

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

Answer 2

我正要发布答案，但 @Cruise Liu 抢先了我。我会尝试解释一下。它是一种整数分区，但您不需要生成元素，因为您只对“元素数量”感兴趣。即最终答案 3 而不是 {1, 2, 3}

给定一个数字 N，您还有另一个限制，即数字不能重复。因此，最好的情况是 N 实际上是一个数字，例如 1、3、6、10、15

i.e. f(x) = x * (x + 1) / 2. 

例如，取 6。 f(x) = 6 存在。具体来说 f(3) = 6 。这样你就得到答案3。

这意味着，如果存在一个整数 X，且 f(x) = N，则存在一组数字 1, 2, 3 ... x，将其加起来得出 N。这就是最大数可能（无需重复）。

然而，在 f(x) = N 中，有时 x 不是整数。

f(x) = x * (x + 1 ) / 2 = N
i.e. 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 )

IE

int max_partition_length(int n){
    return (int)((-1.0 + sqrt(1 + n*8))/2);
}