Ninja and Crazy sum

Easy
0/40
Average time to solve is 15m
11 upvotes
Asked in company
Codenation

Problem statement

Ninja is learning summation and is interested in performing summation on a matrix. Standing at a particular row and column, he is interested in adding all the column values to the right of it and belonging to the same row and not including the present column value. He performs such operations at every row and column of the matrix. Can you return the final matrix that Ninja gets?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of rows and the number of columns respectively.

 Each of the next ‘N’ lines of the test case contains ‘M’ space-separated integers denoting ‘M’ integers of every row respectively.
Output Format: 
For each test case, print the resultant matrix.
Note: 
You are not required to print the expected output or take the matrix input; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^3
1 <= M <= 10^3
-10^5 <= input[i][j] <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
1 2
2 3
1 1
2
Sample Output 1 :
 3 0
 0
Explanation for Sample Input 1 :
In the first test case, we are taking a matrix of size 1*2, and standing at (0,0) we add the value of all column elements to its right. There is only one element so the value at (0,0) becomes 3. Now moving to (0,1). There is no element to the right of it. So the value stored here will be 0. So the resultant matrix is [3 0].

In the second test case, we are taking a matrix of size 1*1, and standing at (0,0), we add the value of all column elements to the right. There is no one element to the right so the value at (0,0) is 0, so the final matrix is [0].
Sample Input 2 :
2
3 3
1 2 3
4 5 6
7 8 9
2 2
1 2
3 4
Sample Output 2 :
5 3 0
11 6 0
17 9 0
2 0
4 0
Hint

 Can you calculate the sum of elements starting from right?

Approaches (1)
Brute force

The key here is to traverse all the lines sequentially, and for each line, we calculate the required sum at the given index.

 

The steps are as follows:

  • We initialize a variable ‘sum’ to 0, which will be storing the value of the sum from the right.
  • We will iterate over all the rows, i.e., i = 0 to i = N - 1:
    • We will iterate over all the columns in backward order, i.e., j = M-1 to 0:
      • We store the value of matrix[i][j] in a variable ‘temp’.
      • We replace the value of matrix[i][j] with sum.
      • We increment the value of the sum by matrix[i][j].
  • We will return the matrix as the final answer.
Time Complexity

O(N*M), where N is the number of rows and M is the number of columns.

 

As we are traversing every element of the matrix of size N * M, we get an overall complexity of O(N * M).

Hence the overall time complexity is O(N*M). 

Space Complexity

O(N*M), where N is the number of rows and M is the number of columns.

 

We are using a matrix, to store the pattern. Hence, the overall space complexity is O(N*M). 

Code Solution
(100% EXP penalty)
Ninja and Crazy sum
Full screen
Console