_codervoder_'s blog

By _codervoder_, history, 7 days ago, In English,

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 !

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
7 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    7 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
7 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Actually if N is large, we can just consider it a string and use map. That'd do.