<p>You are given an <code>m x n</code> binary matrix <code>matrix</code>.</p>

<p>You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from <code>0</code> to <code>1</code> or vice versa).</p>

<p>Return <em>the maximum number of rows that have all values equal after some number of flips</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[0,1],[1,1]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> After flipping no values, 1 row has all values equal.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[0,1],[1,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> After flipping values in the first column, both rows have equal values.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[0,0,0],[0,0,1],[1,1,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> After flipping values in the first two columns, the last two rows have equal values.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>matrix[i][j]</code> is either&nbsp;<code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
int maxi=0;
struct node{
    int cnt;
    node* child[2];
    node(){
        cnt=0;
        child[0]=NULL;
        child[1]=NULL;
    }

};
//count of number of rows which are same or compliment of each other 
//used a trie to get to the solution
node* insert(node*curr, vector<int>&row, int i){
    if(!curr){
        curr= new node;
    }
      if(i==row.size()){
        curr->cnt++;
        maxi=max(curr->cnt, maxi);
        return curr;
    }
    curr->child[row[i]]=insert(curr->child[row[i]],row,i+1);
    return curr;
}

    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        int nums[m];
        node *root=new node;
        vector<int>a={1,0,0,1};
        insert(root,a,0);
        for(int i=0;i<m;i++){
            insert(root,matrix[i],0);
        }
        for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        matrix[i][j]=1-matrix[i][j];
         for(int i=0;i<m;i++){
            insert(root,matrix[i],0);
        }
        return maxi;
        
    }
};
69600