CareerCup

If the array is of size N, and we are required to do k (>= 1) iterations, then it is possible to do this in O(k) time (yes, independent of N!), using the following observations:

Observation 1)

If at some intermediate step the array was x_1, x_2, ..., x_M and we then performed one iteration on it, to get x_2 - x_1, ..., x_M - x_{M-1}, the sum of the elements is x_M - x_1.

Thus if you want to find the sum after k iterations, you need to find the first and last element after k-1 iterations and subtract.

Observation 2)

After r iterations, x_1, x_2, ..., x_M, the first element becomes

x_{r+1} - r x_r + (r choose 2) x_{r-1} - (r choose 3) x_{r-2} + ...

Similar formula can be given for the last term.

(Yes, those are binomial coefficients).

Observation 3)

r choose 0, r choose 1, r choose 2, ... r choose r, can be computed in O(r) time, by computing r choose t in O(1) time after already having computed r choose (t-1).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SumAfterIterations
{
    class Program
    {
        //A = {5, 3, 8, 9, 16} 
        //After one iteration A = {3-5,8-3,9-8,16-9}={-2,5,1,7} 
        //After second iteration A = {5-(-2),1-5,7-1} sum =7+(-4)+6=9 
        //Given an array, return sum after n iterations
        static void Main(string[] args)
        {
            int[] A = new int[] { 5, 3, 8, 9, 16 };
            int iterations = 12;
            int ans = SumAfterNIterations(A, iterations);
            Console.WriteLine("answer is {0}", ans);
        }

        static int SumAfterNIterations(int[] array, int iterations)
        {
            int sum = 0;
            if (array == null) return 0;
            if (array.Length == 1) return array[0];
            if (iterations < 1)
            {
                foreach (int i in array)
                    sum += i;
                return sum;
            }
            int len = array.Length;
            int round = 0;

            while (len > 1 && round++ < iterations)
            {
                sum = 0;
                for (int i = 0; i < len - 1; i++)
                {
                    array[i] = array[i + 1] - array[i];
                    sum += array[i];
                }
                len--;
            }
            return sum;
        }
    }
}

Dupe of question?id=16390676.

There is an O(n) solution there, which uses Pascal's triangle.

void GetSum(array<int> input, int N)
{
	if(N == 0)
	{
		int sum = 0;
		for(int i = 1; i < input.length; i++)
		{
			sum += input[i] ;
		}
		return sum;
	}

	if(input.length == 1)
	{
		return 0;//error 
	}
	int temp[input.length -1];
	for(int i = 1; i < input.length; i++)
	{
		temp[i-1] = input[i];
	}
	
	for(int j = 0; j < temp.length; j++)
	{
		temp[j] = temp[j] - input[j];
	}

	GetSum(temp, N--);

}

public int getSum(int[] input, int n) {
		
		if (n ==0) {
			int sum = 0;
			for(int i=0; i<input.length; i++) {
				sum += input[i];
			}
			return sum;
		}
		int[] b = new int[input.length-1];
		for (int i=0; i<input.length-1; i++) {			
			b[i] = input[i+1] -input[i];
		}
		n--;
		return getSum(b,n);
		 
	}

Obviously it's recursion.

public class ArraySum {
  public static int getSum(int[] a, int n) {
    if (a.length < n || n == 1) {
      int sum = 0;
      for (int e : a) {
        sum += e;
      }
      return sum;
    }
    int[] b = new int[a.length - 1];
    for (int i = 0; i < b.length; i++) {
      b[i] = a[i + 1] - a[i];
    }
    return getSum(b, n - 1);
  }

  public static void main(String[] args) {
    int[] a = {5, 3, 8, 9, 16};
    System.out.println(getSum(a, 3));
  }
}

public long sumFromArray(int iNoOfIterations, int [] arrValues) {
		long lSum = 0;
		if(iNoOfIterations >= arrValues.length || iNoOfIterations < 0) return -1L;
		if(iNoOfIterations == 0) for(int i = 0; i < arrValues.length; i++) lSum += arrValues[i];
		else {
			int iToCalc = 1;
			while (iToCalc <= iNoOfIterations) {
				int [] newArray = new int[arrValues.length - 1];
				for(int i = 0; i < arrValues.length; i++) {
					newArray[i] = (arrValues[i + 1] - arrValues[i]);
					if(iToCalc == iNoOfIterations) lSum += newArray[i];
					if( (i + 1) == arrValues.length - 1 ) break;
				}
				arrValues = newArray;
				iToCalc++;
			}
		}
		return lSum;
	}

Here is the solution in C#

int[] array = {5,3,8,9,16};
int length = array.Length;
int[] inner = new int[4];
for(int k = 0;k<2;k++)
{
for(int i=1,j=0;i<length;i++,j++)
{
inner[j]=array[i]-array[i-1];
}
length = length - 1;
for(int l = 0;l< length;l++)
array[l] = inner[l];
}

inner.Take(length).Sum().Dump();

inner.Dump();

From your example looks like it is a1-a2 and not a2-a1

//
// sum of numbers
//
#include<stdio.h>
main(){
int a[5]={4,6,8,3,6},c=0,i;
for(i = 0; i < 5; i++){
c += a[i];
}
printf("%d",c);
}

1) Here the sum is always first number in array - last number in array for the subsequent array.

2) So we have to find the first number and last number in the previous array.

3) For that we have to find a magic number which is as follows:
Iteration1: 1
which means 1st number = 1*a[0] ;second number = 1*a[n-1]

Iteration2: 10 +1 =11
which means 1st number = 1*a[0] -1*a[1] ; 2nd Number = 1*a[n-1] -1 *a[n-2];

Iteration3: 110 +11 =121
which means 1st number = 1*a[0] -2*a[1]+1*a[2] ; 2nd Number =1*a[n-1] -2 *a[n-2]+1*a[n-3]

Iteration4: 1210+121 =1331


Return firstnumber - secondnumber;

I'm not big on pasting links of previous solutions. Here is the solution I worked out, and checked against the previous link. It appears to have the same outcome, with some minor syntactical differences. The solution in the pasted link actually runs a sum on all elements at each new grouping. My algorithm takes advantage of the fact that each rows sum is equal to the previous rows firstElement - previous rows lastElement to save on computational power.

public static int operation(int[] a, int c){
        int first = 0;
        int last = 0;
        int sum = 0;
        int count = 0;
        int length = a.length;
        
        if(length == 1) {return a[0];}
        if(c == 0){
            for(int i = 0; i < a.length; i++){
                sum += a[i];
            }
            return sum;
        }
        
        while(length > 1 && count < c){
            first = a[0];
            last = a[length-1];
            
            for(int i = 0; i < length-1; i++){
                a[i] = a[i] - a[i+1];
                System.out.println(a[i] + " loop");
            }
            length--;
            count++;
        }
        
        sum = first - last;
        return sum;
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args){
        int[] main = {4,6,8,3,6};
        int it = 6;
        int result;
        
        result = operation(main, it);
        System.out.println(result);
    }

sites.google.com/site/spaceofjameschen/home/array/compute-the-sum-of-elements-in-after-nth-iteration-for-below-operation-on-array

class SumArray {
    public static int sumOfArray(int[] A) {
        if ( (A.length <= 0) || (A.length == 1) ) {
            return(A[0]);
        }
        else if (A.length == 2) {
            return(A[1] - A[0]);
        }
        else {
            int[] B = new int[A.length - 1];
            for(int i=1; i<A.length; i++) {
                B[i-1] = A[i] - A[i-1];
            }
            return(sumOfArray(B));
        }
    }
    public static void main(String[] args) {
        int[] items = {4, 24, 68, 112};
        System.out.println(sumOfArray(items));
    }

}