Tutorialspoint.dev

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



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<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
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.
?>

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

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter