C Program to Check if a Matrix is a Sparse Matrix

Sparse matrix is a matrix with the majority of its elements equal to zero. However, there is no fixed ratio of zeros to non-zero elements. But it is believed that the number of 0’s should be strictly greater than half of the product of rows and columns in a matrix.

Example 1:

Given matrix:

The above matrix contains a total of 5 zeros’, which is roughly 17% of all the elements in the matrix. This is a very less number, so this matrix cannot be called a sparse matrix.

Example 2:

Given matrix:

The Above matrix contains a total of 10 zeros’, which is roughly 84% of all the elements in the matrix. This is a huge number, so this matrix can be called a sparse matrix.

Write a C program to check if a given matrix is a sparse matrix. If the matrix is sparse, display “Given matrix is sparse matrix,” otherwise display “Given matrix is not a sparse matrix.”

A sparse matrix is a matrix with the majority of its elements equal to zero. To identify a sparse matrix, we will check all the elements in the sparse matrix one by one and count the number of 0’s. If the number of zeros’ is greater than 50% of the total elements, then the matrix can be called sparse matrix.

Here is source code of the C program to determine if a given matrix is a sparse matrix. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
 * C program to determine if a given matrix is a sparse matrix.
 * Sparse martix has more zero elements than nonzero elements.
 */
 
#include <stdio.h>
 
void main ()
{
    static int array[10][10];
    int i, j, m, n;
    int counter = 0;
 
    printf("Enter the order of the matix \n");
    printf("Enter the number of rows in array: ");
    scanf("%d", &m);
    printf("Enter the number of columns in array: ");
    scanf("%d", &n);
 
    printf("Enter the co-efficients of the matix: \n");
    for (i = 0; i < m; ++i)
    {
        for (j = 0; j < n; ++j)
        {
            scanf("%d", &array[i][j]);
            if (array[i][j] == 0)
            {
                ++counter;
            }
        }
    }
    if (counter > ((m * n) / 2))
    {
        printf("The given matrix is sparse matrix \n");
    }
    else
        printf("The given matrix is not a sparse matrix \n");
    printf("There are %d number of zeros", counter);
}

1. In this C program, we are reading the order of the matrix row and column using ‘m’ and ‘n’ variables respectively.
2. Using for loop the coefficient elements of the matrix is assigned to the variable ‘array[i][j]’.
3. Using if condition statement, check the coefficient element values of the matrix are equal to zero. 4. If the condition is true then it will execute if condition statement and increment the count variable value.
5. The sparse matrix has more zero elements than non zero elements of the matrix.
6. To check the given matrix is sparse matrix or not the if-else condition statement is used to check the multiplication of row and column of the matrix value of ‘m’ and ‘n’ variables respectively.
7. When dividing the element values by 2 its value should be less than the number of zero elements counted by the value of ‘counter’ variable.
8. If the condition is true, then it will display the “given matrix is sparse“. Otherwise, it will display the “given matrix is not a sparse matrix” and displays the number of zeros counted in the matrix.

Time complexity: O(m*n)
The above program for checking whether a matrix is sparse matrix or not has a time complexity of O(m*n) since the two loops are executed, first the outer loop runs |rows| times, and then the inner loop runs |columns| times.

Space complexity: O(m*n)
The above program for checking whether a matrix is sparse matrix or not has a space complexity of O(m*n), where m = number of rows and n = number of columns.

Test Case 1: In this case, we enter “5” for the number of rows and “6” for the number of columns as input for checking whether a matrix is sparse matrix or not.

Enter the order of the matix 
Enter the number of rows in array: 5
Enter the number of columns in array: 6
Enter the co-efficients of the matix:
12	23	11	0	12	0
0	34	67	0	7	43
5	0	78	7	65	2
7	2	98	34	67	1
12	3	675	1	3	2
 
The given matrix is not a sparse matrix 
There are 5 number of zeros

Test Case 2: In this case, we enter “4” for the number of rows and “3” for the number of columns as input for checking whether a matrix is sparse matrix or not.

Enter the order of the matix 
Enter the number of rows in array: 4
Enter the number of columns in array: 3
Enter the co-efficients of the matix:
0	0	0
0	1	0
0	0	0
5	0	0
 
 
The given matrix is a sparse matrix 
There are 10 number of zeros

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.