check if a given matrix is sparse or not in C++

Hello,
In this tutorial, we will learn how to check if a matrix is sparse or not in C++, with an example, algorithm, and a C++ program.

A sparse matrix is a matrix of m row and n column in which most of the elements are zero. That is if the number of zeros in the matrix is greater than (m*n/2) then we can say that the matrix is sparse.

How to check if a given matrix is sparse or not in C++

Let’s take an example to see how a sparse matrix looks like.

Example:

Conside a 5*4 matrix.
input matrix:
                1 0 0 2 
                4 5 6 0 
                0 1 2 0 
                0 0 0 0 
                1 0 0 7

In the matrix, there are 5*4 = 20 numbers and by counting the number of zeros, 
we can see that there are 11 number of zeros which is more than the half of total
number of elements of matrix.
Therefore, the matrix is a sparse matrix.

Conside a 3*3 matrix. 
input matrix:
              1 0 3
              4 5 0
              7 0 9

In the matrix, there are 3*3 = 9 numbers and by counting the number of zeros, 
we can see that there are 3 number of zeros which is less than the half of total
number of elements of matrix.
Therefore, the matrix is not a sparse matrix.

Algorithm

declare and initialize a matrix of m*n. (where m and n are the lengths of row and column of matrix)
declare a variable to count the number zeros in the matrix. (Consider “count”).
Travers the matrix from start to end and whenever zero encounter increment count by 1.
if the count is greater than m*n/2 then the matrix is sparse, else it is not.

C++ program to check a given matrix is sparse or not

#include <bits/stdc++.h>
using namespace std;

//Function to return number of zero in matrix
int isSparse(int matrix[][50], int m, int n){

    int count = 0;

    for(int i = 0; i < m; i++)
        for(int j = 0; j< n; j++)
            if(matrix[i][j] == 0)
                count++;
    
    return count;
}

int main(){
    int matrix[50][50], n, m;

    //taking input for size of row and column
    cout<<"Enter the size of row of the  matrix: ";
    cin>>m;
    cout<<"Enter the size of column of the matrix: ";
    cin>>n;

    //Taking input in the matrix
    cout<<"\nInput the elements of matrix.\n";
    for(int i = 0;i < m; i++)
        for(int j = 0; j < n; j++)
            cin>>matrix[i][i];
    
    if(isSparse(matrix, m, n) > (m * n)/2)
        cout<<"\nThe matrix is sparse.";
    else
        cout<<"\nThe matrix is not sparse. ";

    return 0;
}

Output:

Enter the size of row of the  matrix: 5
Enter the size of column of the matrix: 4

Input the elements of matrix.
1 0 0 2
4 5 6 0
0 1 2 0
0 0 0 0
1 0 0 7

The matrix is sparse.

Time Complexity:

O(m*n), where m and n is the length of row and column of the matrix

you may also read: