Single value computation

Question

I'm writing code to compute a single value answer to a given numbers in integer array such that step sum is calculated till only 1 number is left.

For example:

Input:

3,5,2,6,7

Output is computed as:

(3+5)+(5+2)+(2+6)+(6+7)

It remains like this till I only have a single number left.

3 5 2 6 7
 8 7 8 13
 15 15 21
 30 36
 66

int inputarray={3,5,2,6,7};
int inputlength=inputarray.length;
 while(inputlength!=0)
 { 
 for(int i=0;i<inputlength-1;i++)
 {
 inputarray[i]=inputarray[i+1]+inputarray[i]; 
 }
 inputlength--;
 }
 System.out.println(inputarray[0]);

It computes the result in quadratic growth. Is there any way to compute my result more efficiently? What else can I do to improve it?

Answer 1

So spoke Tartaglia

An optimized solution should make use of the Tartaglia's Triangle that is so constructed:

 1
 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1

You could generate it or memorize it, your choice.

The solution is simply multiplying input with Tartaglia's Triangle coefficients of the nth row where n is the total number of input, as multipliers and then adding all together.

Show don't tell

for a in range(10):
 for b in range(10):
 for c in range(10):
 assert tree_addition([a,b,c]) == a + b*2 + c
for a in range(10):
 for b in range(10):
 for c in range(10):
 for d in range(10):
 assert tree_addition([a,b,c,d]) == a + b*3 + c*3 + d
for a in range(10):
 for b in range(10):
 for c in range(10):
 for d in range(10):
 for e in range(10):
 assert tree_addition([a,b,c,d,e]) == a + b*4 + c*6 + d*4 + e

Should explain my point more clearly, note the the code above always works.

Answer 2

First of all it is always helpful to format your code properly (I now used the default code convention for Java):

int inputarray={3,5,2,6,7};
int inputlength=inputarray.length;
while (inputlength != 0) { 
 for (int i = 0; i < inputlength-1; i++) {
 inputarray[i] = inputarray[i+1] + inputarray[i]; 
 }
 inputlength--;
}
System.out.println(inputarray[0]);

Also it is better to test for inputlength < 0 because then the termination of the loop is much more likely...

For performance tuning:

Try to create a formula for your problem to calculate the result. Your example could be reduced to 3 + 4*5 + 6*2 + 4*6 + 7...

Find a formula such like Gauss did for summing up the parts...

• Uwe Plonus: @gds For addition there should be a formula. For substraction/muiltiplication it should also be possible to find one (even though don't know one and would create one myself...). If you want to have flexible operations it is much more difficult and then it also does not belong here but much more to Mathematics as it is no more programming related.

Answer 3

So spoked newton...

public int compute(int... values) {
 int res = 0;
 int length = values.length;
 int current_coeff = 1;
 for (int i = 0; i < length /2; i++) {
 res += values[i] * current_coeff;
 res += values[length -1 -i] * current_coeff;
 current_coeff = current_coeff * ( length - (i+1)) / (i+1);
 }
 if (length % 2 == 0) {
 res += values[length /2]*current_coeff;
 }
 return res;
}

Replace the multiplication by current_coeff by exponentiation for a formula of multiplication.