Interview question - Finding numbers

I just got this question on a SE position interview,开发者_开发百科 and I'm not quite sure how to answer it, other than brute force:

Given a natural number N, find two numbers, A and P, such that:

N = A + (A+1) + (A+2) + ... + (A+P-1)

P should be the maximum possible.

Ex: For N=14, A = 2 and P = 4

N = 2 + (2+1) + (2+2) + (4+2-1) N = 2 + 3 + 4 + 5

Any ideas?

---

If N is even/odd, we need an even/odd number of odd numbers in the sum. This already halfes the number of possible solutions. E.g. for N=14, there is no point in checking any combinations where P is odd.

Rewriting the formula given, we get:

N = A + (A+1) + (A+2) + ... + (A+P-1)
    = P*A + 1 + 2 + ... + (P-1)
    = P*A + (P-1)P/2 *
    = P*(A + (P-1)/2)
    = P/2*(2*A + P-1)

The last line means that N must be divisible by P/2, this also rules out a number of possibilities. E.g. 14 only has these divisors: 1, 2, 7, 14. So possible values for P would be 2, 4, 14 and 28. 14 and 28 are ruled our for obvious reasons (in fact, any P above N/2 can be ignored).

This should be a lot faster than the brute-force approach.

(* The sum of the first n natural numbers is n(n+1)/2)

---

With interview questions, it is often wise to think about what is probably the purpose of the question. If I would be asking you this question, it is not because I think you know the solution, but I want to see you finding the solution. Reformulating the problem, making implications, devising what is known, ... this is what I would like to see.

• If you just sit and tell me "I do not know how to solve it", you immediately fail the interview.

• If you say: I know how to solve it by brute force, and I am aware it will be probably slow, I will give you some hints or help you to get you started. If that does not help, you most likely fail (unless you show some extraordinary skills to compensate for the fact you are probably lacking something in the field of general problem analysis, e.g. you will show how to implement a solution paralelized for many cores or implemented on GPU).

• If you bring me a ready solution, but you are unable to derive it, I will give you another similar problem, because I am not interested about solution, I am interested in your thinking.

---

A + (A+1) + (A+2) + ... + (A+P-1) simplifies to P*A + (P*(P-1)/2) resp P*(A+(P-1)/2).

Thus, you could just enumerate all divisors of N, and then test each divisor P to the following:

Is A = (N-(P*(P-1)/2))/P (solved the first simplification for A) an integral number? (I assume it should be an integral number, otherwise it would be trivial.) If so, return it as a solution.

---

Can be solved using 0-1 Knapsack solution .

Observation : N/2 + N/2 + 1 > N

so our series is 1,2,...,N/2

Consider the constraints of W=N and vi =1 for all elements, I think this trivially maps to 0-1 knapsack, O(n^2)

---

Here is a O(n) solution.

It uses the property of the sum of an arithmetic progression. S = difference*(first_term + last_term)/2

Here our sum is N, the difference is P and first term is A.

Manipulation the above equation we get some equations and we can iterate P from 1 to n - 1 to get a valid A.

def solve(n,p):
return (2*n - (p**2) + p)/(2*p)

def condition(n,p,a):
if (2*n == (2*a*p) + (p**2) - p) and (a*-1 < 0):
    return True
else:
    return False

def find(n):
for x in xrange(n,-1,-1):
    a = solve(n,x)
    if condition(n,x,a):
        return n,x,a