鉴于N，发现加入到得到n个最大号 [英] Given n, find the maximum numbers added to get n

问题描述

问题在Oracle interview.For例如问，如果我的输入为6，则

Question asked in oracle interview.For example,if my input is 6, then

• 5 + 1 = 6答：2


• 4 + 2 = 6答：2


• 3 + 2 + 1 = 6答：3

所以，最后的答案应该是3（即3,2,1都需要得到一笔6）

So, the final answer should be 3.(i.e 3,2,1 are needed to get sum 6)

注意：号码不能重复（即1 + 1 + 1 + 1 + 1 + 1 = 6）

Note:Repetition of number isn't allowed (i.e 1+1+1+1+1+1=6)

我解决了使用递归，但采访并不满足。是动态编程可能吗？

I solved it using recursion but interviewer wasn't satisfied. Is Dynamic Programming possible?

推荐答案

我要发布的答案，但@Cruise刘打我给它。生病尝试解释它一下。
它是一个整数类型划分，但你不需要生成的元素，因为你只在'元素的个数'感兴趣。即，最终的答案3和不{1，2，3}

I was about to post the answer but @Cruise Liu beat me to it. Ill try explaining it a bit . Its a type of integer partitioning but you dont need to generate the elements since you're only interested in the 'number of elements'. i.e. the final answer 3 and not {1, 2, 3}

给出一个数N，你有号码不能重复其他限制条件。
因此最好的情况是如果N实际上是一个数字表示1，3，6，10，15

Given a number N, you have another restriction that numbers cannot repeat. Hence the best case would be if N is actually a number say 1, 3, 6, 10, 15

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

例如，取6 F（X）= 6的存在。具体地说F（3）= 6。因此，你得到的答案3。

For example, take 6. f(x) = 6 exists. specifically f(3) = 6 . Thus you get the answer 3.

这意味着，如果有存在对于函数f（x）= N，则存在一组数字1，2，3的整数X ... X，当相加给予N.这是可能的（不repitition）的最大数量。

What this means is that if there is an integer X that exists for f(x) = N, then there is a set of numbers 1, 2, 3 ... x that when added up give N. And this is the maximum number possible (without repitition).

但是，也有在函数f（x）的情况下= N，其中x不为整数。

However, there are cases in f(x) = N where x is not an integer.

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

解决这个二次我们得到

Solving this quadratic we get

由于数字x是不是消极的，我们不能有

Since the number x is not negative we can't have

因此​​，我们留下了

有关N = 6

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

A perfect Integer. But for N = 12

是8.845 / 2，它是一小部分。地板值是4，这是问题的答案。

which is 8.845 / 2 which is a fraction. The floor value is 4, which is the answer.

在短期：实现功能
F（N）=（int）的（（-1.0 + SQRT（1 + 8 * N））/ 2.0）

In short: Implement a function 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);
}

这篇关于鉴于N，发现加入到得到n个最大号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！