CODEWITHSUNDEEP
algorithmmultidimensional-arraydata-structures
zonyang
zonyang

Reputation: 878

Sum of multidimensional Array

I need to compute the sum of a multidimensional Array. require no extra space, no recursion. 

class MultiDimensionArray {
    // This is a provided function, Assume it works
    public static Long getValue(int... indexOfDimension) {
        //... 
        return value;
    }
    // lengthOfDeminsion: each dimension's length, assume it is valid: lengthOfDeminsion[i]>0.
    public static Long sum(MultiDimensionArray mArray, int[] lengthOfDeminsion) { 
        ...
        return sum;
    }

How to implement the sum() method? it seems like I need to implement a "n level nested loop". 

for() {
    for () {
        ...  
    }
}

I can do this via recursion, but without recursion I really don't know how to achieve this.

Upvotes: 0

Views: 510

Answers (1)

yacc
yacc

Reputation: 3386

It's unclear to me what no extra space means. But my idea is to allocate an n-tuple (n = number dimensions) and a few helper variables.

int n = lengthOfDimension.Length;
int[] tuple = new int[n]; // all zeroes
int at = n-2;
Long sum = 0;
do
{
    for (tuple[n-1] = 0; tuple[n-1] < lengthOfDimension[n-1]; tuple[n-1]++)
    {
        sum += getValue(tuple);
    }
    while (at >= 0 && ++tuple[at] == lengthOfDimension[at])
    {
        tuple[at--] = 0;
    }
    if (at >= 0) at = n-2;
}
while (at >= 0);

The work horse here is the for loop that iterates over the lowest dimension of the hypercube, using tuple to select the right row. Subsequently, values in tuple will be incremented until the respective dimension length is hit, where the value is reset to zero and the next higher one (at-1) is incremented. The task is done when tuple[0] has wrapped.

Upvotes: 1

Related Questions