Algorithms question: flipping columns

This could be possible code:

int candidateRowCount=0;
void populateHash(int *input, int **hash, int col)
{
    bool found = false;
    for (int i=0; i<candidateRowCount; i++)
    {
        for (int j=0; j<col; j++)
        {
            if(input[j] !=hash[i][j])
                break;
            else
            {
                if (j==(col-1))
                {
                    found = true;
                    hash[i][col] +=1;
                }
            }
        }
    }

    if (!found)
    {   // save current candidate Row  in hash to be used for comparison in else block of above steps of this function 
        for (int i=0; i<col; i++)
        {
            hash[candidateRowCount][i] = input[i];
        }
        hash[candidateRowCount][col] +=1;
        candidateRowCount++;
    }
}

int getMaxCount(int** input, int N , int M, int K)
{
    int **hash= new int *[N];
    // an extra column to save frequency of row i
    for(int i=0; i<M+1; i++)
    {
        hash[i]= new int[M+1];
        hash[i][M] =0;
    }
    for(int i=0; i<N; i++)
        for(int j=0; i<M; j++)
            hash[i][j]=0;

    for(int i=0; i<N; i++)
    {
        int count = 0;
        for (int j=0; j<M; j++)
        {
            if(input[i][j]==0)
                count++;
        }
        if(count<=K)
        {
            int diff= K-count;
            if ((diff >= 0) && ((diff %2)== 0))
            {
                populateHash(input[i], hash, M);
            }
        }
    }

    int maxVal = 0;
    for (int i=0; i<candidateRowCount; i++)
    {
        if(hash[i][M]>maxVal)
            maxVal = hash[i][M];
    }
    return maxVal;
}

int main()
{
    freopen("input.txt", "r", stdin);
    int testcase;
    cin >> testcase;
    for (int t=0; t<testcase; t++)
    {
        int N,M,K;
        cin >> N >>M;
        cin >>K;
        int **input = new int *[N];
        for (int i=0; i<N; i++)
            input[i] = new int [M];
        for (int i=0; i<N; i++)
        {
            for (int j=0; j<M; j++)
            {
                cin >> input[i][j];
            }
        }
        int val= getMaxCount(input, N, M, K);

        cout << "Max Val" <<val << endl;
        candidateRowCount= 0;
    }
    return 0;
}

Let's begin by thinking about an important detail of the problem: if two rows contain a column that differ across the rows (for example, in one row it's a zero and in one row it's a one), then there is no possible way to make both rows all ones. To see this, suppose that row x has a zero in some column and row y has a one in that column. Then if we don't flip that column, row x can't be all ones, and if we do flip the column then row y can't be all ones. Consequently, if we take a look at the original matrix and try to think about what rows we are going to make all ones, we are essentially just going to pick some set of rows that are all equal to one another. Our goal is then to pick the set of identical rows that is as large as possible and can be made into all ones using exactly k flips. Let's say that a row that can be made into all ones using exactly k flips is a "candidate row.". Then we just need to find the candidate row in the matrix that appears the greatest number of times.

The actual algorithm for doing this depends on whether or not we are allowed to flip the same column twice. If we aren't, then a candidate row is one that has exactly k zeros in it. If we can flip the same column multiple times, then this is a bit trickier. To make the row all ones, we would need to convert each zero to a one, then would need to keep spending the remaining flips flipping the same column twice to avoid changing any one to a zero. This is true if the difference between k and the number of zeros in the row is a nonnegative even number.

Using this, we get the following algorithm:

1. Maintain a hash table mapping from candidate rows to their frequency.
2. For each row:
   1. Count the number or zeros in the row.
   2. If the difference between k and this number is a nonnegative even number, update the hash table by incrementing the frequency of this particular row.
3. Find the candidate row in the hash table with the greatest total frequency.
4. Output the frequency of that row.

Overall, on an m x n matrix (m rows, n columns), we visit each row once. During the visit, we do O(n) work to count the number of zeros, then O(1) work to see if it is valid. If so, it takes an expected O(n) time to update the hash table, since the hashing step takes O(n) time to hash the row. This means that we spend O(mn) time filling in the table. Finally, the last step takes time O(m) to find the max frequency row, for a net runtime of O(mn), which is linear in the size of the input. Moreover, this is asymptotically optimal, since if we spent less time than this we couldn't look at al, the matrix elements!

Hope this helps! This is a cool problem!

If the k columns have to be different, the answer is easy: find the row with k zeros which occurs most frequently, and flip the columns to fix these rows. If you can flip a column more than once, find the most frequently occuring row whose number of zeroes is no greater than k and has the same parity.

The first solution works since any other method will not fix as many rows. The second method works since you can throw away any even number of flips in order to pick the most favorable kind of row to try to fix... do this by flipping any unused column an even number of times.

Sorry if this is a gross misinterpretation of your problem.