Количество ячеек в двоичной матрице, имеющих одинаковое побитовое XOR для этой строки и столбца

Дана бинарная матрица arr[][] из N строк и M столбцов. Задача состоит в том, чтобы найти количество ячеек в матрице, где побитовое исключающее ИЛИ всех элементов в ее строке и столбце равны.

Примеры:

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.

Подход: Идея решения проблемы с использованием массива префиксов Xor и жадного подхода заключается в следующем:

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.

Выполните следующие шаги, чтобы решить эту проблему:

• Во-первых, предварительно вычислить xor всех элементов каждой строки и столбца отдельно.
• Выполните итерацию по каждой ячейке матрицы, пусть текущая ячейка будет (i, j), где i — индекс строки, а j — индекс столбца.
  • Если xor всех элементов строки i и столбца j равен, увеличьте счетчик на единицу.
• Вернуть счет .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N*M), так как мы используем вложенные циклы для прохождения N*M раз.

Вспомогательное пространство: O(N+M), так как мы используем дополнительное пространство для строк и столбцов массивов.