26 Sep 2020 - Hadron DaVinci
Given a square matrix, calculate the absolute difference between the sums of its diagonals.
For example, given the square matrix A is shown below,
the first line is n, the number of rows and columns.
All rows below n represent the actual numbers in the square matrix.
A = """3
1 2 3
4 5 6
9 8 9
"""
In this example:
The left diagonal = 1+5+9=15 The right to left diagonal = 3+5+9 Their absolute difference is |15-17|=2
Given:
- the matrix is expressed as a list of row_lists, - where i is the column position of an element, - and j is the row position of an element, - n is the max rows or columns
Then the following is True:
1. when i==j, that number is on the left diagonal 2. when i==(n-1) - j, that number is on the right diagonal
Time Complexity: O(N)
Spatial Complexity: 1
step0:
define variables that represent the sum of the left and right diagonals and initialize them as 0
step1
loop through each number.
step2:
while looping,
if number is on the left diagonal, then add it to the left diagonal sum.
if number is on the right diagonal, then add it to the right diagonal sum.
A = """3
1 2 3
4 5 6
9 8 9
"""
def on_left_diagonal(i, j):
return i == j
def on_right_diagonal(i, j, n):
return i == (n-1) - j
def extract_data(_str_input):
lines = _str_input.split("\n")
n = int(lines[0]) # get n
matrix_data = lines[1:] # skip the first line
return n, matrix_data
def find_absolute_difference_of_diagonals(_str_input):
n, matrix_data = extract_data(_str_input)
left_diagonal_count = 0
right_diagonal_count = 0
for j, line in enumerate(matrix_data):
numbers_str = line.split(" ") # 1 2 3 #4 5 6 #9 8 9 #\n
for i, number_str in enumerate(numbers_str):
if number_str == "": continue
number = int(number_str)
if on_left_diagonal(i, j):
left_diagonal_count += number
if on_right_diagonal(i, j, n):
right_diagonal_count += number
absolute_difference = abs(left_diagonal_count - right_diagonal_count)
return absolute_difference
result = find_absolute_difference_of_diagonals(A)
print('Answer is:', result)
Answer is: 2