# Count entries equal to x in a special matrix

You are given a square matrix (matrix[][]) of order n, where matrix[i][j] = i*j. Find the number of cells which have entry equal to a given number x.
NOte : Indexing of matrix starts from 1, i.e. 1<= i,j <= n.

Examples :

```Input : matrix[][] = {1, 2, 3, 4,
2, 4, 6, 8,
3, 6, 9, 12,
4, 8, 12, 16}
x = 4
Output : 3

Input : matrix[][] = {1, 2, 3, 4,
2, 4, 6, 8,
3, 6, 9, 12,
4, 8, 12, 16}
x = 12
Output : 2

```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple Approach is to traverse the whole of matrix and check whether cell value is equal to given x and then increase count value accordingly. Time complexity in this approach is quite high and is equal to O(n^2).

```// traverse and check whole matrix
for (int i=1; i<=n ; i++)
{
for (int j=1; j<=n; j++)
if (i * j == x)
count++;
}
// return count
return count;
```

An efficient approach is to only find the number of factors of given x in the range 0 to x and also those factors (including divisor and quotient ) must be less than or equal to n (order of matrix). In this case time complexity will be O(n).

```// traverse and find the factors
for (int i=1; i<=n && i<=x ; i++)
{
// x%i == 0 means i is factor of x
// x/i <= n means i and j are <= n (for i*j=x)
if ( x/i <= n && x%i ==0)
count++;
}
// return count
return count;
```

## C++

 `// CPP program for counting number of cell  ` `// equals to given x ` `#include ` `using` `namespace` `std; ` ` `  `// function to count factors as number of cell ` `int` `count (``int` `n, ``int` `x) ` `{ ` `    ``int` `count == 0; ` `    ``// traverse and find the factors ` `    ``for` `(``int` `i=1; i<=n && i<=x ; i++) ` `    ``{ ` `        ``// x%i == 0 means i is factor of x ` `        ``// x/i <= n means i and j are <= n (for i*j=x) ` `        ``if` `( x/i <= n && x%i ==0) ` `            ``count++; ` `    ``} ` `    ``// return count  ` `    ``return` `count; ` `} ` ` `  `// driver program ` `int` `main() ` `{ ` `    ``int` `n = 8; ` `    ``// we can manually assume matrix of order 8*8 ` `    ``// where mat[i][j] = i*j , 0

## Java

 `// Java program for counting number of ` `// cell equals to given x ` `class` `GFG ` `{ ` `    ``// function to count factors as  ` `    ``// number of cell ` `    ``static` `int` `count (``int` `n, ``int` `x) ` `    ``{ ` `        ``int` `count = ``0``; ` `     `  `        ``// traverse and find the factors ` `        ``for` `(``int` `i = ``1``; i <= n && i <= x ; ` `                                    ``i++) ` `        ``{ ` `            ``// x%i == 0 means i is factor ` `            ``// of x. x/i <= n means i and ` `            ``// j are <= n (for i*j=x) ` `            ``if` `( x / i <= n && x % i == ``0``) ` `                ``count++; ` `        ``} ` `         `  `        ``// return count  ` `        ``return` `count; ` `    ``} ` ` `  `    ``// driver program ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``8``; ` `         `  `        ``// we can manually assume matrix  ` `        ``// of order 8*8 where  ` `        ``// mat[i][j] = i*j , 0

## Python3

 `# Python 3 program for counting  ` `# number of cell equals to given x  ` ` `  `# function to count factors  ` `# as number of cell  ` `def` `count(n, x): ` `    ``cnt ``=` `0` ` `  `    ``# traverse and find the factors  ` `    ``for` `i ``in` `range``(``1``, n ``+` `1``): ` ` `  `        ``# // x%i == 0 means i is factor of x  ` `        ``# x/i <= n means i and j are <= n (for i*j=x)  ` `        ``if` `i <``=` `x: ` `            ``if` `x ``/``/` `i <``=` `n ``and` `x ``%` `i ``=``=` `0``: ` `                ``cnt ``+``=` `1` `    ``return` `cnt ` ` `  `# Driver code ` `n ``=` `8` `x ``=` `24` `print``(count(n, x)) ` ` `  `# This code is contributed by Shrikant13 `

## C#

 `// C# program for counting number ` `// of cell equals to given x ` `using` `System;  ` ` `  `class` `GFG { ` `     `  `    ``// function to count factors as  ` `    ``// number of cell ` `    ``static` `int` `count (``int` `n, ``int` `x) { ` `         `  `        ``int` `count = 0; ` `     `  `        ``// traverse and find the factors ` `        ``for` `(``int` `i = 1; i <= n &&  ` `             ``i <= x ; i++) ` `        ``{ ` `             `  `            ``// x%i == 0 means i is factor ` `            ``// of x. x/i <= n means i and ` `            ``// j are <= n (for i*j=x) ` `            ``if` `( x / i <= n && x % i == 0) ` `                ``count++; ` `        ``} ` `         `  `        ``// return count  ` `        ``return` `count; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 8; ` `         `  `        ``// we can manually assume matrix  ` `        ``// of order 8*8 where  ` `        ``// mat[i][j] = i*j , 0

## PHP

 ` `

Output :

```4
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

Matrix Matrix

code

load comments