### omggg's blog

By omggg, 3 years ago, Given array and m. Find the index i such that A[i]%m is maximum. What is the best method to do that if I have incoming queries of m.

Any help is much appreciated, thanks :)  Comments (11)
 » 3 years ago, # | ← Rev. 2 →   One Possible Approach may be, Sort the Array $A$ For every $i$, you iterate over all it's multiples $x, x \le 2max(A)$, and find the maximum $a_i < x$. This should have the same complexity as of Sieve, i.e $M\log M$ with $M = max(m)$. However for this the limits should be $a_i,m \leq 10^6.$You may want to try 484B - Maximum Value
•  » » 3 years ago, # ^ | ← Rev. 2 →   too costly since there are queries for it, anyways thanks :)
•  » » » You can answer queries in O(1) I guess with the pre-computation.
 » Say M is max possible m. Then there's $O(n\log{n} + n\sqrt{M} + q\sqrt{M}\log{n})$ solution. For each $m < \sqrt{M}$ calculate the answer naively, that takes $O(n\sqrt{M})$. Then sort the array to anwer other queries. For other m decompose the array into segments such that for each segment $l ... r$ $\lfloor{}\frac{a_l}{m}\rfloor{} = \lfloor{}\frac{a_{l+1}}{m}\rfloor{} = ... = \lfloor{}\frac{a_r}{m}\rfloor{}$. The answer is $max(a_r\mod{m})$ for each right boundary of each segment. There are $O(\sqrt{M})$, but i don't know if there's a way to decompose the array faster than $O(\sqrt{M}\log{n})$
 » I have $O(n + q + M\cdot log(M))$ solution where $M$ is maximum over all m.For each $1 \le m \le M$ calculate answer. Every number $x$ can be written as $x = y \cdot m + r$, where $y = \lfloor \frac{x}{m} \rfloor$ and module remainder $r < m$. Iterate over all $m$ and $y$ ($1 \le m \le M, 0 \le y \le \lfloor \frac{M}{m} \rfloor$). Now find maximum $a[i] < y \cdot m + m$ and update answer for $m$ as $a[i]$ % $m$ (you need store result for fast search maximum $a[i]$). Time complexity is $O(\sum_{m=1}^{M}\frac{M}{m}) = O(M\cdot log(M))$ (harmonic series).