Summed Matrix

Easy

0/40

Average time to solve is 10m

Contributed by

13 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
4 2
3 4

Sample Output 1:

1
3

Explanation of the Sample Input1:

Test case 1:

The matrix we get after using M(i,j) = i+j is:

2 3 4 5 
3 4 5 6 
4 5 6 7
5 6 7 8

Only cell (1,1) is having the value 2. Hence the value of ‘q’ is 1 here.

Test case 2:

2 3 4
3 4 5
4 5 6

Here the cells (1,3),(2,2),(3,1) are having the value 4 hence the value of 'q' is 3.

Sample Input 2:

2
1 2
2 3

Sample Output 2:

1
2

Explanation of the Sample Input 2:

Test case 1:
Here only cell (1,1) is having the value 2. Hence the value of 'q' is 1.

Test case 2:
Both diagonal cells ((2,1)(1,2)) are having sum 3 hence the answer is 2.

Hint 1

Hint 2

Make the matrix and see how many cells are having value q.

Approaches (2)

Approach 1

Approach 2

Brute Force

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’

Time Complexity

O(N^2), where ‘N’ is the size of the array.

Here we are nesting two loops, one is going from 1 to ‘N’ and the second is going from ‘1’ to ‘N’ for every ‘i’ in the first loop, making the time complexity N^2.

Space Complexity

O(1), as we use constant space.

(100% EXP penalty)

Summed Matrix

Console