# Find the sum of Z shape in the given matrix

Nov 1, 2020

--

Approach1:

Simple algorithm

• n := row count of matrix
• if n <= 2, then
• return sum of all elements in matrix
• first_row := sum of first row
• last_row := sum of last row
• diagonal = sum of matrix[i, n-1-i] for all i from 1 to n-2
• return first_row + last_row + diagonal
class SumZshape:
def solve(self, matrix):
n = len(matrix)
if n <= 2:
return sum(sum(row) for row in matrix)
first_row = sum(matrix[0])
last_row = sum(matrix[n-1])
diagonal = sum(matrix[i][n-1-i] for i in range(1, n-1))
return first_row + last_row + diagonal

Approach 2:

Let’s add the horizontal parts of the Z first. There are 3 cases: n=0, 1, or 2+.

Now let’s add the diagonal. The notation matrix[i][~i] means the i-th last element of the i-th row of matrix.

The unary ~ (invert) operator yields the bitwise inversion of its integer argument. The bitwise inversion of x is defined as -(x+1). It only applies to integral numbers.

https://docs.python.org/3/reference/expressions.html#unary-arithmetic-and-bitwise-operations

So for example:

print(~1)= -2

class SumZshape:
def solve(self, matrix):
n = len(matrix)
ans = 0
if n >= 1:
ans += sum(matrix[0])
if n >= 2:
ans += sum(matrix[-1])
for i in range(1, n - 1):
ans += matrix[i][~i]
return ans

Input

matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]

Output

35