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

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 what 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

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

C++ program to check whether 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][j];
    
    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 are the length of the row and column of the matrix

you may also read:

1. Find trace and normal of matrix in C++
2. Rotate a Matrix in C++ ( Clockwise and Anticlockwise )