Bnahmad15's blog

The Mostly repeated number in range query
By Bnahmad15, history, 6 years ago, In English

given an array of integers with (N <= 1e6) and Q (Q <= 1e6) queries with L and R.. what is the mostly repeated number in range [L,R] ? is there any fast way to work it out ?

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

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

That is the range mode query problem. It has a lot of solution in with either just Sqrt-decomposition or MO's algorithm. You can also do it with bitset.

If you know that the number of times the mode appears in the range is large, you can refer to this problem.

→ Reply