Count entries equal to x in a special matrix

0 0 5 minutes read

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

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) and space complexity O(1).

// 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) and space complexity O(1).

// 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;

Implementation:

C++

// CPP program for counting number of cell 
// equals to given x
#include<bits/stdc++.h>
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<i,j<=n
    int x =  24;
    cout << count(n, x);
    return 0;
} 

Java

// Java program for counting number of
// cell equals to given x
import java.io.*;
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<i,j<=n
        int x = 24;
        System.out.println(count(n, x));
    }
}
 
/*This code is contributed by Danish kaleem*/

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<i,j<=n
        int x = 24;
        Console.Write(count(n, x));
    }
}
 
// This code is contributed by Nitin Mittal.

PHP

<?php
// PHP program for counting 
// number of cell equals to
// given x
 
// function to count factors
// as number of cell
function c_ount ( $n, $x)
{
    $Count = 0;
    // traverse and find the factors
    for ( $i = 1; $i <= $n and
                  $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 and
                  $x % $i == 0)
            $Count++;
    }
    // return count 
    return $Count;
}
 
// Driver Code
$n = 8;
 
// we can manually assume 
// matrix of order 8*8
// where mat[i][j] = i*j , 
// 0<i,j<=n
$x = 24;
echo c_ount($n, $x);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// Javascript program for counting number of cell 
// equals to given x
 
// function to count factors as number of cell
function count (n, x)
{
    var count = 0;
    // traverse and find the factors
    for (var 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
var n = 8;
// we can manually assume matrix of order 8*8
// where mat[i][j] = i*j , 0<i,j<=n
var x =  24;
document.write( count(n, x));
 
</script>

Output

Time Complexity: O(n)
Auxiliary Space: O(1), since no extra space has been taken.

If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!