Maximum rows with all 1s after T column flips
Filed under Oracle
Free read 2 of 3Confirm if flips must be exactly T or at most T, and how identical row patterns can be grouped.
The question
Given a binary matrix of size M x N and an integer T, where a column flip inverts all bits in that column, find the maximum number of rows that can contain all 1s after performing at most T column flips (or exactly T flips depending on parity rules).
Constraints
- 1 <= M, N <= 100
- 0 <= T <= N
- Matrix elements are 0 or 1.
Examples
- Input
- matrix = [[0,1],[1,0]], T = 1
- Output
- 1
- Why
- Flipping column 0 makes the first row [1, 1], giving 1 row with all 1s.
Approach
Confirm if flips must be exactly T or at most T, and how identical row patterns can be grouped.
Try all possible combinations of choosing T columns to flip, then count rows with all 1s. O(C(N, T) * M * N).
For each row, determine the minimum flips needed to make it all 1s (i.e. count its zeros). If a row's zeros count z <= T and (T - z) % 2 == 0, that row configuration can be achieved. Count frequencies of identical row patterns and find the maximum frequency among valid rows.
T exceeds N, T has different parity than row zeros, matrix with all zeros or all ones.
Tips
- What they are testing: Test with T=0, T greater than number of columns, and matrices where all rows are identical.
- Common mistake: Not realizing that any row can be made of all 1s if and only if the number of 0s in that row is <= T and (T - count_zeros) is even.
Related Oracle questions
Collected from public candidate posts and coding forums. Updated Nov 2026.