5
\$\begingroup\$

Given

You are given a square matrix of size \$N×N\$. Calculate the absolute difference of the sums across the two main diagonals.

Input Format

The first line contains a single integer N. The next N lines contain N integers (each) describing the matrix.

Constraints

\$1\leq N \leq 100\$

\$−100 \leq A_{i} \leq 100\$

Solution

def diagonal_difference(matrix):
    l = sum(matrix[i][i] for i in range(N))
    r = sum(matrix[i][N-i-1] for i in range(N))
    return abs(l - r)

matrix = []
N = input()
for _ in range(N):
    matrix.append(map(int, raw_input().split()))

print diagonal_difference(matrix)

Is there more elegant solution for the given problem. Also, I am getting intuition that I can use reduce, is that possible?

\$\endgroup\$

3 Answers 3

10
\$\begingroup\$

Instead of indexing to access the rows, you could use iteration:

l = sum(row[i] for i, row in enumerate(matrix))

Instead of doing two passes over matrix to calculate l and r, you could accumulate the difference in one pass: (note also negative indexing from end of list)

difference = sum(row[i] - row[-i-1] for i, row in enumerate(matrix))
return abs(difference)

The single-pass approach would also allow you to process input line by line, instead of storing the whole matrix in memory.

\$\endgroup\$
3
\$\begingroup\$

My big concern with this approach is that you store the entire matrix before doing any processing. Since the size of the matrix is \$O(N^2)\$, you could run into occupancy problems for large \$N\$.

A simpler approach would be to get the contribution to the difference with each row of the matrix, as you read it. You're only ever storing a single row at once.

That is:

N = int(raw_input())
difference = 0
for i in xrange(N):
    row = raw_input().split()
    difference += (int(row[i]) - int(row[N-1-i]))
print abs(difference)

A few other items of note here:

  • I'm getting N via a raw_input() call, not input(). In general you should be wary of using input() and evaluating arbitrary code from the user.

    (Although that advice only applies to Python 2; in Python 3 the names have changed.)

  • In Python 2, using xrange() is preferable to range() because it doesn't create a list for the entire range.

  • I'm being lazy about the coercion to int(), and reducing from \$N^2\$ calls to \$2N\$ calls.

\$\endgroup\$
1
  • \$\begingroup\$ I usually like to think in terms of pure functions which takes some input and returns the result. \$\endgroup\$
    – CodeYogi
    Sep 22, 2015 at 6:02
1
\$\begingroup\$

You don't pass N to diagonal_difference, that's bad practice. You should either be passing it as a parameter, or at least determining it within the function since it's just len(matrix). Also N isn't a good name, just because the question used that doesn't mean you need to. Code has different requirements than a brief. Maybe matrix_size or some other explicit name.

It's also odd to have raw_input() when you're actually expecting input. Putting at least ">" is recommended so that the user can see that the script is waiting for input, not just running code silently.

\$\endgroup\$
3
  • \$\begingroup\$ I think you are advocating pure functions regarding N. Seems good to me. \$\endgroup\$
    – CodeYogi
    Sep 22, 2015 at 5:35
  • \$\begingroup\$ input should be avoided by @alexwlchan \$\endgroup\$
    – CodeYogi
    Sep 22, 2015 at 5:56
  • \$\begingroup\$ Here it is stackoverflow.com/a/4915408/4260745 \$\endgroup\$
    – CodeYogi
    Sep 22, 2015 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.