JavaScript program: Count the number of sets of 1's and 0's in a binary matrix

A binary matrix is ​​a matrix consisting of only two numbers, which, as its name suggests, are 1 and 0. In this article, we will go through codes and proper explanations to understand the concepts better. In this tutorial, we will write a JavaScript program to count the set of 1s and 0s in a given binary matrix.

Problem introduction

In this problem, we are given a binary matrix and we need to find the set of rows or columns that contain the same value. A set can be a single value or be of any size, provided that it contains identical elements from rows or columns. For example,

We have a binary matrix with two rows and three columns that looks like this -

1 0 1
0 0 1

The number of sets of 1 and 0 can be calculated as

• Set of size 1 − All the cells of the matrix are distinct sets in itself and there is a total of 6 cells.

• Set of size 2 - The first two columns of the second row have the same value, the second and third columns also have the same value, there are 2 sets of size 2 and have A collection of identical values. There are two more 1's in the first line which can be considered as a set

• Collection of size 3 - The maximum possible collection size in the matrix is ​​the maximum size of the rows and columns, which is 3 here. However, for size, no set containing the same value is available.

So we have 6, 3 and 0 sets available for sizes 1, 2 and 3 respectively. So ultimately our answer will be 9.

method

In the previous section, we have seen that we have to focus on only a particular row or column to get the number of similar elements in it. Also, we will use a mathematical concept to count the number of sets with different sizes present in a particular row or column.

For example, if we have the total number of x 1's in a row, the total number of sets of 1's of different sizes 1 to x will come from the permutations.

Let’s turn to this approach -

• First, we will get an array containing zeros and ones, or the given binary matrix.

• We will create a function that automatically calculates the required answer for any matrix passed to it as a parameter and returns the answer as a return value.

• In this function, we will iterate over the array or binary matrix twice, once by rows and second time by columns.

• In the for loop, we will maintain two variables, one for storing the number of 1's and the other for storing the number of 0's.

• After iterating through a single row or column, we will update the answer using the formula seen above and store the answer in our variable.

• Finally, we will return the answer by removing the row*column from it since we have added them twice.

We have removed the row * column because when iterating over the rows the set is added with a single value of two zeros and a one and again when iterating over the columns.

The Chinese translation of

Example

is:

Example

Let’s see the implementation of the above steps to better understand the concepts -

// given variables
var cols = 3; // no of columns
var rows = 2; // no of rows
// function to solve the problem with passed array 
function fun(arr) {
   // variable to store the final answer 
   var ans = 0;
   // traversing over the rows using for loop 
   for (var i = 0; i < rows; i++) {
      var ones = 0, zeroes = 0;
      for ( var j = 0; j < cols; j++) {
         if (arr[i][j] == 1)
         ones++;
         else
         zeroes++;
      }
      // increasing the answer on the basis of current count based on ones 
      ans = ans + Math.pow(2, ones)-1;
      // based on zeros 
      ans = ans + Math.pow(2, zeroes)-1;
   }
   //traversing over the columns using for loop 
   for (var i = 0; i < cols; i++) {
      var ones = 0, zeroes = 0;
      for ( var j = 0; j < rows; j++) {
         if (arr[j][i] == 1)
         ones++;
         else
         zeroes++;
      }
      //increasing the answer on the basis of current count based on ones 
      ans = ans + Math.pow(2, ones)-1;
      // based on zeros 
      ans = ans + Math.pow(2, zeroes)-1;
   }
   return ans - (rows * cols);
}
var arr = [ [ 1, 0, 1 ], [ 0, 1, 0 ] ];
console.log("Total number of the sets in the given binary matrix is: " + fun(arr));

Time and space complexity

The time complexity of the above code is O(N*N), where N is the maximum value of the number of rows and columns of the given matrix.

No extra space is used, so the space complexity of the code is O(1).

in conclusion

In this tutorial, we learned how to write a JavaScript program that counts the number of sets of 1s and 0s in a given binary matrix. A binary matrix is ​​a matrix that contains only two numbers, which, as its name suggests, are 1 and 0. The code in question has time complexity O(N*N) and space complexity O(1).

The above is the detailed content of JavaScript program: Count the number of sets of 1's and 0's in a binary matrix. For more information, please follow other related articles on the PHP Chinese website!