alwaysGREEEN's blog

Interview Problem
By alwaysGREEEN, history, 6 years 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

Comments Comments (8)
| Write comment?
»
6 years 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.

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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?

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
»
6 years 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.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It can be established that the rows that become 1 in the end are same in the beginning. So, keep a count of the frequency of every distinct row and since we have to perform exactly k operations, find the row with maximum frequency and (noOfZeros — k)%2 == 0. The answer is the frequency of that row.

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

    I have slight doubt over the second condition, like what if k < noOfZeros, then we wont be able to convert all the zeroes to one, so we will need to have one more condition that is noOfZeros must be less than or equal to k.

    → Reply