Reminder: in case of any technical issues, you can use lightweight websites m1.codeforces.com, m2.codeforces.com or m3.codeforces.com ×

### alwaysGREEEN's blog

By alwaysGREEEN, history, 6 months ago, ,

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.

•
• -2
•

 » 6 months ago, # |   +1 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<
 » 6 months ago, # |   +6 I think I came across a similar problem a few days ago. In that problem the constraints were like this: N ≤ 20 and M ≤ 105. So we can represent every row as an integer which will be less than 220. 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 1st and the 3rd row 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 than K, that is the answer (the frequency of that number).Anyway, if in your problem, the constraint on N is large, then I don't know how to solve it. Maybe some DP approach will work.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 In that case how is the answer for k=2 equal to 1.If we sort by frequency101-1 102-2the 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?
•  » » » 6 months ago, # ^ |   0 I missed a small thing. You have to divide the frequency by number of 0's in the row.
•  » » » » 6 months ago, # ^ |   0 Sir can you please provide code for the question! that would be pretty helpful!
•  » » 6 months ago, # ^ |   0 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?
•  » » » 6 months ago, # ^ |   0 Did the simple brute force get accepted, also can u tell me about the constraints on k, m,n?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 For small input it works. am not sure about large input. Constraints n ≤ 20 and n ≤ 10^5..
 » 6 months ago, # |   +5 Actually if N is large, we can just consider it a string and use map. That'd do.
 » 6 months ago, # |   0
 » 5 months ago, # |   +8 Hint: The rows that become all-1-rows in the end are equal to each other in the beginning.