Hello Friends, I recently faced a problem in my coding interview that i was unable to solve. The problem statement is -

A binary matrix of nxm was given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s.

for eg, n=3, m=3,

1 0 0 1 0 1 1 0 0

if k=2, then we will toggle column 2 and 3 once and we will get rows 1 and 3 with 1 1 1 and 1 1 1 i.e. all 1’s so answer is 2 as there are 2 rows with all 1’s.

if k=3, then we will toggle column 2 thrice and we will get row 2 with 1 1 1 i.e. all 1’s so answer is 1 as there is 1 row with all 1’s.

Please help me solve this question !

For small input, you could use backtracking, with a time complexity of: O(m) * O(m^k) = O(m^(k+1)) = O(m^k). You use an array (or bitmask) for saving if the column i (0 <= i < m) is toggled or not.

Also, you could try to speed your solution using DP + bitmask, with two states:

k: number of toggles left toggled: integer, toggled & (1<<i) is true if the column i is toggled and false if not.

The time complexity of this solution is: O(m) * O(k) * O(2^m)

Although these solutions, maybe you're asking for a faster one. I hope that I helped you anyway.

I think I came across a similar problem a few days ago. In that problem the constraints were like this:

N≤ 20 andM≤ 10^{5}. So we can represent every row as an integer which will be less than 2^{20}. Now an observation is that, if we make 2 different rows to all 1's, then they must have been the same before any flipping. As in your example, you can see that the 1stand the 3rdrow is same (Think why this happens). So, as we represented each row as a number, we can keep count of the numbers and we can sort them with respect to their frequency. After that, the first number which has a frequency less thanK, that is the answer (the frequency of that number).Anyway, if in your problem, the constraint on

Nis large, then I don't know how to solve it. Maybe some DP approach will work.In that case how is the answer for k=2 equal to 1.

If we sort by frequency

101-1 102-2

the first frequency which is less than k(2) is 1. so the answer should be 1 but the answer for this case is 2. Tell me where i am going wrong?

I missed a small thing. You have to divide the frequency by number of 0's in the row.

Sir can you please provide code for the question! that would be pretty helpful!

I also faced this coding test on a interview. I am not sure my approach is good one or not. What I did was, I tried to take the combination of all columns based on the given K. If k = 2, then it'll return the columns (0,1), (1,2), (0,2) and then I toggled them to check out if that gives the maximum or not. And I also kept twice combination (as it was said in the test) as sometimes, one column can be scanned twice. As, No- STL was allowed. I had to use normal 2D array. How can I improve this code?

Did the simple brute force get accepted, also can u tell me about the constraints on k, m,n?

For small input it works. am not sure about large input. Constraints n ≤ 20 and n ≤ 10^5..

Actually if

Nis large, we can just consider it a string and use map. That'd do.https://stackoverflow.com/questions/7116438/algorithms-question-flipping-columns

Hint: The rows that become all-1-rows in the end are equal to each other in the beginning.