Last Updated: 9 Dec, 2020

Multiplication Matrix

Moderate

Asked in company

Solve now

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 ) }

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.

Solve now

Approaches

01 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’.

Solve now

02 Approach

It's easy to see that the number ‘K‘ can appear in column ‘i’ only once, in row ‘K’ / ‘i’. For every column ‘i’, let's check that ‘K’ divides ‘i’ and ‘K’ / ‘i’, where ’i’ ≤ N. If all requirements are met, we'll update the answer.

Algorithm :

1. Initialize variable ‘numAppearance’ to 0.
2. Iterate through 1 to ‘N’ (say, iterator ‘i’).
3. Check if ‘K’ divides ‘i’ leaving remainder as zero, then assign ‘j’ as ‘K’ / ‘i’, and then check if ‘i’ * ’j’ equals ‘k’ and also ‘j’ is lesser than or equal to ‘N’, then, increment the variable ‘numAppearance’.
4. Return ‘numAppearance’.

Solve now