Given n, find the maximum numbers added to get n

Question

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

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

So, the final answer should be 3.(i.e 3,2,1 are needed to get sum 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?

Answer 1

The minimum sum of x numbers is

So just find x that satisfies the inequality:

Here's the code:

#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;
}

You can use binary search if n is very large.

Answer 2

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}

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. 

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

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).

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

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

So we're left with

For N = 6

A perfect Integer. But for N = 12

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

In short: Implement a function f(N) = (int) ((-1.0 + sqrt(1 + 8*N))/2.0 )

i.e.

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