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:

\(\begin{bmatrix}
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
\end{bmatrix}\)

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:

advertisement
advertisement
\(\begin{bmatrix}
0 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 0\\
5 & 0 & 0
\end{bmatrix}\)

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.

Problem Description

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

Problem Solution

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.

Note: Join free Sanfoundry classes at Telegram or Youtube
Program/Source Code

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);
}
Program Explanation

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.

advertisement

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.

Runtime Test Cases

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.

advertisement
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”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.