Continuously get the difference of integers in an array until the array size becomes one-CodePudding

I have an array:

int[] array= {5, 7, 16, 3, 2}

I want to develop an application that takes the difference of the elements up to a single element in the array.

Array → {5, 7, 16, 3, 2}
[1] Loop → {2, 9, -13, -1}
[2] Loop → {7, -22, 12}
[3] Loop → {-29, 34}
[4] Loop → {63}

The result of the algorithm to be developed should be 63 in this case. How can I develop this algorithm?

CodePudding user response：

I'm not sure about an application, but I can help with the function. Your goal can be accomplished with only a few lines of code if you use recursion. If the array that is passed is of length one, the value is returned. This will happen after as many recursive steps as are needed. It would be good to include an exception if the passed array is of length 0, but that is not strictly necessary.

public int takeDifferences(int[] arr){
    if (arr.length > 1) {
        int[] newArr = int[arr.length - 1];
        for (int i = 0; i < arr.length - 1]; i  ) {
            newArr[i] = arr[i   1] - arr[i];
        }
        takeDifferences(newArr);
    }
    else {
        return arr[0];
    }
}

CodePudding user response：

It is a pity you did not dive into this trying to derive rules, applying some cleverness. (That is what gives the most fun.)

It is indeed a variant of Pascal's triangle as commented. You can do it symbolically, without regarding to the array values, and derive a formula for an array of (n 1) elements.

n (max index)	formula
0	a0
1	-a0 a1
2	a0 - 2.a1 a2
3	-a0 3-a1 -3.a2 a3
4	a0 - 4.a1 6.a2 - 4.a3 a4

The binomial formula fits with a coefficient of a[i] being: -(-1)ⁱ.(n over i). The proof I will leave to you.

5 - 4*7   6*16 - 4*3   2 = 7 - 40   96 = 63

CodePudding user response：

Try this:

    int[] temp = {5, 7, 16, 3, 2};
    int[] temp2 = new int[temp.length];
    while (temp.length > 1) {
        temp2 = new int[temp2.length - 1];
        for (int i=0; i < temp.length - 1; i  ) {
            temp2[i] = temp[i   1] - temp[i];
        }
        temp = temp2;
        System.out.println(Arrays.toString(temp));
    }