Multiplication Matrix

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in company
Codenation

Problem statement

You are given an integer ‘N’ denoting the size of a 'N' * 'N' square matrix 'mat', and an integer ‘K’.

The elements of matrix ‘mat’, holds a special property i.e. 'mat[i][j]' = i * j .Where 0 < i,j <= N. Your task is to return the occurrence of integer ‘K’ in the matrix ‘mat’.

Consider 1 based indexing.

Note: 
You are not given the actual matrix. Only the size of the matrix 'mat' is given.

Example:

For ‘N’ = 5 and ‘K’ = 5 :
The count of cells in the 5 * 5 matrices that contain the number ‘5’ will be 2. 
 { ( 1, 5 ), ( 5, 1 ) }
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer 'N' denoting the number of rows and columns.

The next line of each test case contains an integer ‘K’.
Output Format : 
For each test case, return an integer denoting the number of occurrences of ‘K'in the matrix ‘mat’.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^4
1 <= K <= 10^9

Time Limit: 1 sec.
Sample Input 1 :
2
10
5
8
16
Sample Output 1:
2
3
Explanation For Sample Output 1 :
For N = 10 and K = 5, the required number of cells will be 2 {(1, 5), (5, 1)}.
For N = 8 and K = 16, the required number of cells will be 3 {(2, 8), (8, 2), (4, 4)}.
Sample Input 2:
2
10
2
2
1
Sample Output 2:
2
1
Hint

Element ‘K’ can be in any cell starting from (1, 1) to (N, N). Can you think of a solution now?

Approaches (2)
Naive Approach

In this approach, we will check every element and count the occurrences of ‘K’.


Algorithm :

 

  • Initialize the variable ‘COUNT’ to 0.
  • Iterate through 1 to ‘N’ (say, iterator ‘i’).
    • Iterate through 1 to ‘N’ (say, iterator ‘j’).
      • Check if ‘MAT[ i ][ j ]’ equals ‘K’, then, increment the ‘COUNT’.
         
Time Complexity

O(‘N’^2), where ‘N’ is the number of rows and columns.

 

As we are traversing every element in the 2-D matrix, hence, time complexity will be O(N^2).

Space Complexity

O(1),

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Multiplication Matrix
Full screen
Console