kingofnumbers's blog

Finding minimum number using maximum range query
By kingofnumbers, history, 9 years ago, In English

Hello

I have a question that come to my mind but I'm not able to solve it:

Given N , you know there's an array of N integers but you don't know integers of the array , you only know N.

you want to find minimum integer of this array, in order to do that you can ask questions of form: L R

it means what's the maximum number among all integers from index L to R (inclusive)

you will know the index and the value of the maximum integer

in case we can ask O(N) questions then we can query every integer alone and get the minimum one

but is there's any way to know the minimum integer of this array using less than O(N) questions ?

if there's no way how to prove that formally?

  • Vote: I like it
  • +22
  • Vote: I do not like it

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

I don't think there's a better way.

If your array contains N-1 "10" and 1 element "1" at position id, all your Range Max Queries will return you 10 (and so will be useless) except RMQ(id, id)

Since you don't know what is id, you'll have to try all RMQ(x, x) in order to know where your "1" is.

So, the worst case complexity is O(N), but maybe there is a better average case complexity (I unfortunately can't help you for this ^^)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Thank you , you have reduced the problem to linear search so of course there will be no better average number than N/2 tries which is O(N)

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +34 Vote: I do not like it

You need at least N questions.
To prove it, let's play this game! You are asking questions and I answer. If you ask me the maximum number from interval [l, r], I'll tell you the maximum number is l'th one and it's value is 1.
If you ask less than N questions, it means there is some i that you have never asked me any interval in form [i, R], so you don't know if i'th number is 1 or 0, so you can't be sure what is the minimum number of the array.

→ Reply