CODEWITHSUNDEEP
algorithmcomputer-science
Aadesh P
Aadesh P

Reputation: 245

Algorithm - Based On Finding The Maximum Number Of Matches

I came across a problem that I still can't figure out how to solve. I figured out how to do it the brute force way, but it does not work when there are thousands of elements.

Problem: 
Say you are given the following input:
T F T F T F
T T F T T F
T F F T T T
F T F F T T
T F F T T T

You can inverse columns such as:
T         F
F         T
T   -->   F
F         T
T         F

And you want to find the maximum number of matches you can get given the input "2D table", such that a match means a row with the same element. You are only allowed to inverse columns, and you can inverse as many columns as you want, but you just need to find the most number of matches you can get. For Example:

T F T
F T F     has only one match "T T T", but if we invert column 1 and 3 it 
T T T     becomes

F F F
T T T     which has two matches "F F F" and "T T T", which is the most 
F T F     number of matches possible for that table.

Also, the number of columns and rows can be any number less than 100,000. How would you exactly do this efficiently?

Upvotes: 0

Views: 192

Answers (1)

Brent Washburne
Brent Washburne

Reputation: 13148

Maybe I'm missing something, but a quick run down the rows should answer your question.

Start with the top row, and flip each column as needed until the top row is all T. Count the number of matches. Repeat for every other row, finding if the count is greater than any previous row.

You don't need to invert the whole matrix so each row is all F, the count will be the same.

Upvotes: 1

Related Questions