Given a binary matrix arr[][] of N rows and M columns. The task is to find the number of cells in the matrix, where Bitwise XOR of all the elements in its row and column are equal.
Examples:
Input: N = 2, M = 2, arr[][] = [[0, 0], [1, 0]]
Output: 2
Explanation: There are a total of 4 cells.
Out of which only 2 cells satisfy the above condition.
Cell {0, 1} and {1, 0} (indexing is 0 based).Input: N = 2, M = 2, arr[][] = [[1, 0], [0, 1]]
Output: 4
Explanation: There are a total of 4 cells.
Out of which all of the 4 cells satisfy the condition.
If we take any of the cells then the xor of all the elements
in their row and column is equal to 1.
Approach: The idea to solve the problem using prefix Xor array and greedy approach is as follows:
Pre-compute the xor value of all the elements in each row and column.
Then for each cell (cell (i, j))check whether the xor value of all the elements of that row i and that column j is equal or not.
Follow the below steps to solve this problem:
- Firstly, pre-compute the xor of all the elements of each row and column separately.
- Iterate through each cell of the matrix, let the current cell be (i, j) where i is the row index and j is the column index.
- If the xor of all the elements of row i and column j is equal then increase the count one.
- Return the count.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the count of cellsint countCells(vector<vector<int> >& v){ // n = number of rows and // m = number of columns int n = v.size(), m = v[0].size(); vector<int> row(n), col(m); // Pre-compute the xor of all the // elements of each row. for (int i = 0; i < n; i++) { int val = 0; for (int j = 0; j < m; j++) { val ^= v[i][j]; } row[i] = val; } // Try to pre-compute the xor of all // the elements of each column. for (int j = 0; j < m; j++) { int val = 0; for (int i = 0; i < n; i++) { val ^= v[i][j]; } col[j] = val; } // Here 'ans' will store the number of // cells that satisfy the condition // of the problem. int ans = 0; // Loop to find the for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the xor value of all the // elements of 'ith' row and // 'jth' column is same then it // is a cell which satisfy // the condition. if (row[i] == col[j]) { ans++; } } } return ans;}// Driver Codeint main(){ vector<vector<int> > arr = { { 1, 0 }, { 0, 1 } }; // Function call cout << countCells(arr); return 0;} |
Java
// Java program for the above approachimport java.io.*; import java.util.*; class GFG{ // Function to find the count of cells static int countCells(int[][] v) { // n = number of rows and // m = number of columns int n = v.length, m = v[0].length; int[] row = new int[n]; int[] col = new int[m]; // Pre-compute the xor of all the // elements of each row. for (int i = 0; i < n; i++) { int val = 0; for (int j = 0; j < m; j++) { val ^= v[i][j]; } row[i] = val; } // Try to pre-compute the xor of all // the elements of each column. for (int j = 0; j < m; j++) { int val = 0; for (int i = 0; i < n; i++) { val ^= v[i][j]; } col[j] = val; } // Here 'ans' will store the number of // cells that satisfy the condition // of the problem. int ans = 0; // Loop to find the for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the xor value of all the // elements of 'ith' row and // 'jth' column is same then it // is a cell which satisfy // the condition. if (row[i] == col[j]) { ans++; } } } return ans; } // Driver Code public static void main(String args[]) { int[][] arr = { { 1, 0 }, { 0, 1 } }; // Function call System.out.println(countCells(arr)); }}// This code is contributed by sanjoy_62. |
Python3
# Python3 code to implement the approach# Function to find the count of cellsdef countCells(v): # n = number of rows and # m = number of columns n, m = len(v), len(v[0]) row, col = [0 for _ in range(n)], [0 for _ in range(m)] # Pre-compute the xor of all the # elements of each row. for i in range(0, n): val = 0 for j in range(0, m): val ^= v[i][j] row[i] = val # Try to pre-compute the xor of all # the elements of each column. for j in range(0, m): val = 0 for i in range(0, n): val ^= v[i][j] col[j] = val # Here 'ans' will store the number of # cells that satisfy the condition # of the problem. ans = 0 # Loop to find the for i in range(0, n): for j in range(0, m): # If the xor value of all the # elements of 'ith' row and # 'jth' column is same then it # is a cell which satisfy # the condition. if (row[i] == col[j]): ans += 1 return ans# Driver Codeif __name__ == "__main__": arr = [[1, 0], [0, 1]] # Function call print(countCells(arr))# This code is contributed by rakeshsahni |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the count of cells static int countCells(int[,] v) { // n = number of rows and // m = number of columns int n = v.GetLength(0); int m = 2; int[] row = new int[n]; int[] col = new int[m]; // Pre-compute the xor of all the // elements of each row. for (int i = 0; i < n; i++) { int val = 0; for (int j = 0; j < m; j++) { val ^= v[i, j]; } row[i] = val; } // Try to pre-compute the xor of all // the elements of each column. for (int j = 0; j < m; j++) { int val = 0; for (int i = 0; i < n; i++) { val ^= v[i, j]; } col[j] = val; } // Here 'ans' will store the number of // cells that satisfy the condition // of the problem. int ans = 0; // Loop to find the for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If the xor value of all the // elements of 'ith' row and // 'jth' column is same then it // is a cell which satisfy // the condition. if (row[i] == col[j]) { ans++; } } } return ans; }// Driver Codepublic static void Main(){ int[,] arr = { { 1, 0 }, { 0, 1 } }; // Function call Console.Write(countCells(arr));}}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript code to implement the approach// Function to find the count of cellsfunction countCells(v){ // n = number of rows and // m = number of columns let n = v.length,m = v[0].length let row = new Array(n).fill(0), col = new Array(m).fill(0) // Pre-compute the xor of all the // elements of each row. for(let i = 0; i < n; i++) { let val = 0 for(let j = 0; j < m; j++) { val ^= v[i][j] } row[i] = val } // Try to pre-compute the xor of all // the elements of each column. for(let j = 0; j < m; j++) { let val = 0 for(let i = 0; i < n; i++) { val ^= v[i][j] } col[j] = val } // Here 'ans' will store the number of // cells that satisfy the condition // of the problem. ans = 0 // Loop to find the for(let i = 0; i < n; i++) { for(let j = 0; j < m; j++) { // If the xor value of all the // elements of 'ith' row and // 'jth' column is same then it // is a cell which satisfy // the condition. if (row[i] == col[j]) ans += 1 } } return ans}// Driver Codelet arr = [[1, 0], [0, 1]]// Function calldocument.write(countCells(arr),"</br>")// This code is contributed by shinjanpatra</script> |
Output
4
Time Complexity: O(N*M), as we are using nested loops to traverse N*M times.
Auxiliary Space: O(N+M), as we are using extra space for arrays row and col.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
