Minimum number of element required to make a sequence that sums to a particular number

Suppose there is number s=12 , now i want to make sequence with the element a1+a2+.....+an=12.

The criteria is as follows-

1. n must be minimum.
2. a1 and an must be 1;
3. ai can differs a(i-1) by only 1,0 and -1.

for s=12 the result is 6.

So how to fi开发者_StackOverflownd the minimum value of n.

---

Algorithm for finding n from given s:

1.Find q = FLOOR( SQRT(s-1) )

2.Find r = q^2 + q

3.If s <= r then n = 2q, else n = 2q + 1

---

Example: s = 12

1. q = FLOOR( SQRT(12-1) ) = FLOOR(SQRT(11) = 3
2. r = 3^2 + 3 = 12
3. 12 <= 12, therefore n = 2*3 = 6

Example: s = 160

1. q = FLOOR( SQRT(160-1) ) = FLOOR(SQRT(159) = 12
2. r = 12^2 + 12 = 156
3. 159 > 156, therefore n = 2*12 + 1 = 25

and the 25-numbers sequence for

159:    1,2,3,4,5,6,7,8,9,10,10,10,9,10,10,10,9,8,7,6,5,4,3,2,1

---

Here's a way to visualize the solution.

First, draw the smallest triangle (rows containing successful odd numbers of stars) that has a greater or equal number of stars to n. In this case, we draw a 16-star triangle.

   *
  ***
 *****
*******

Then we have to remove 16 - 12 = 4 more stars. We do this diagonally starting from the top.

   1
  **2
 ****3
******4

The result is:

  **
 ****
******

Finally, add up the column heights to get the final answer:

1, 2, 3, 3, 2, 1.

---

There are two cases: s odd and s even. When s is odd, you have the sequence:

1, 2, 3, ..., (s-1)/2, (s-1)/2, (s-1)/2-1, (s-1)/2-2, ..., 1

when n is even you have:

1, 2, 3, ..., s/2, s/2-1, s/2-2, ..., 1

---

The maximum possible for any given series of length n is:

n is even => (n^2+2n)/4 n is odd => (n+1)^2/4

These two results are arrived at easily enough by looking at the simple arithmetic sum of series where in the case of n even it is twice the sum of the series 1...n/2. In the case of n odd it is twice the sum of the series 1...(n-1)/2 and add on n+1/2 (the middle element).

Clearly you can generate any positive number that is less than this max as long as n>3.

So the problem then becomes finding the smallest n with a max greater than your target.

Algorithmically I'd go for:

Find (sqrt(4*s)-1) and round up to the next odd number. Call this M. This is an easy to work out value and will represent the lowest odd n that will work.

Check M-1 to see if its max sum is greater than s. If so then that your n is M-1. Otherwise your n is M.

---

Thank all you answer me. I derived a simpler solution. The algorithm looks like-

First find what is the maximum  sum that can be made using n element-

if n=1 ->    1            sum=1;
if n=2 ->    1,1          sum=2;
if n=3 ->    1,2,1        sum=4;
if n=4 ->    1,2,2,1      sum=6;
if n=5 ->    1,2,3,2,1    sum=9;
if n=6 ->    1,2,3,3,2,1  sum=12;


So from observation it is clear that form any number,n  9<n<=12 can be 
made using  6 element, similarly number 
6<n<=9  can be made at using 5 element.
So it require only a binary search to find the number of
 element that make a particular number.