Last Updated: 18 Dec, 2020
Summed Matrix
Easy
Asked in company
A matrix is constructed of size n*n and given an integer ‘q’. The value at every cell of the matrix is given as, M(i,j) = i+j, where ‘M(i,j)' is the value of a cell, ‘i’ is the row number and ‘j’ is the column number. Return the number of cells having value ‘q’.
Assume, the array is in 1-based indexing.
Input Format:-
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
One and only line of each test case contains two space-separated integers ‘n’ and ‘q’ where ‘n’ is the size of the matrix and ‘q’ the value we need to find in the matrix.
Output Format:-
For each test case, print an integer denoting the number of cells having value 'q' in a separate line.
Note:
Don’t print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^5
1 <= n <= 10^18
2 <= q <= (n+n)
Time Limit: 1 sec
Approaches
- We make a variable ‘total’ to store the number of cells having the value q. Initialize ‘total’ to 0.
- Make two nested loops from 1 to n. One ‘i’ from 1 to ‘n’ and for every ‘i’ we make a loop from 1 to ‘n’.
- If at point ‘i+j’=q. We increase the ‘total’ by 1.
- Return the variable ‘total’
Let's take the matrix
2 3 4
3 4 5
4 5 6
Now we can see till 4 all the numbers are occurring number-1 times. And if we take 4 as the longest diagonal the number on both sides at an equal distance have the same number of time occurrence. So after the biggest diagonal, the occurrence is 2*n+1-q.
- If ‘q’ is less than equal to ‘1+n’. Then we return ‘q-1’ as the answer.
- In all other cases, we will return ‘2*n-q+1’ as the answer.