sum of absolute matrix

Question

Here is a question from previous HackerEarth Challenge -

Roy has a matrix of size NxN. Rows and Columns are numbered from 0 to N-1. jth column of ith row contains absolute difference between i and j. In other words, Matrix[i][j] = abs(i-j) where 0 ≤ i, j < N. Your task is to find sum of this matrix i.e.

sum = 0
for i=0 to N-1
    for j=0 to N-1
        sum += Matrix[i][j]

and here is my solution to this problem -

public static long getSum(int num, long acc) {
        if (num == 1)
            return acc;
        long sum = 0;
        for (int i = 0; i < num; i++) {
            sum += i;
        }
        sum = sum * 2;
        return getSum(num - 1, acc + sum);
    }

But this function fails for large number like say anything greater than 4500. I get Stack Over Flow Error. Here I have tried two things basically to keep the code optimized -

use tail recursion, and
keep running time of this function of order 'n'

So please tell me if I have achieved the two things here correctly. If yes what else can I do to optimize this code. Thanks for your help.

MBo · Accepted Answer · 2015-03-05T09:19:21.733

4

The matrix has very simple structure (I draw only top right half, bottom left is the same, mirrored)

0 1 2 3 4 5 ...
. 0 1 2 3 4 ...
. . 0 1 2 3 ...
. . . 0 1 2 ...
. . . . 0 1 ...
. . . . . 0 ...

It is clear that Kth row contains arithmetic progression 0..(N - K - 1), so it's sum is

Sk = (N - K - 1) * (N - K) / 2

and overall sum is (O(N) solution)

S = 2 * Sum[k = 0..N-1] (Sk)

Moreover, while sum of every row is 'triangular' number, sum of triangular numbers is 'Tetrahedral number', and there is closed formula, that leads to O(1) solution

S = 2 * ((N-1)*N*(N+1)/6) = N*(N+1)*(N-1)/3

Example: for N=4 S = 3*4*5/3 = 20

edited Mar 05 '15 at 09:19

answered Mar 05 '15 at 09:13

MBo

77,366
5
53
86

This is one nice answer! – Pham Trung Mar 05 '15 at 09:15
Thanks MBo for your answer. That was really helpful. – Mandeep Rajpal Mar 05 '15 at 10:09

score 1 · Answer 2 · edited May 23 '17 at 11:44

Tail recursion

Tail recursion does not protect you from stack overflow in Java. Some other languages can recognise tail-calls and optimize them during compilation so they do not extend the stack.

...tail call optimization is hard to do in the JVM because of the security model and the need to always have a stack trace available.

(From Does the JVM prevent tail call optimizations?)

It is however easy to replace tail recursions with a loop:

public static long getSum(int num, long acc) {
    while (num > 1) {
        long sum = 0;
        for (int i = 0; i < num; i++) {
            sum += i;
        }
        sum = sum * 2;
        //set up values for next loop
        num--;
        acc += sum;
    }
    return acc;
}

Big-O

keep running time of this function of order 'n'

You have not achieved this. It is clear to see there are 2 nested loops over num, and num is decreasing, I think this makes it O(n log n)

Thanks weston, for sharing this information about tail recursion in java. — Mandeep Rajpal, Mar 05 '15 at 10:06

sum of absolute matrix

2 Answers2

Tail recursion

Big-O