ladygaga's blog

Minimum number of comparisons to check if N matrices are distinct
By ladygaga, history, 9 years ago, In English

Given N marices each of dimention A*B, filled only with 0 or 1.

What is the minimum number of cells you need to check so that you can differentiate between the N matrices?

The answer is log_base_2(N). Can someone explain this answer?

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure I understand the question, but

Suppose AB> N, Suppose N matrices, each having 1 zero and AB-1 ones. You'll need to see all O(N) position where zero is possible to differentiate matricies.

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

    Maybe the problem asks to prove that log(N) is a lower bound.

    → Reply