Databases
StackOverflow2013
Postsdbo
POIs it possible to compute the minimum of a set of numbers modulo a given number in amortized sublinear time?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIs it possible to compute the minimum of a set of numbers modulo a given number in amortized sublinear time?
    text
    copied!<p>Is there a data structure representing a large set <code>S</code> of (64-bit) integers, that starts out empty and supports the following two operations:</p> <ul> <li><code>insert(s)</code> inserts the number <code>s</code> into <code>S</code>;</li> <li><code>minmod(m)</code> returns the number <code>s</code> in <code>S</code> such that <code>s mod m</code> is minimal.</li> </ul> <p>An example:</p> <pre> insert(11) insert(15) minmod(7) -> the answer is 15 (which mod 7 = 1) insert(14) minmod(7) -> the answer is 14 (which mod 7 = 0) minmod(10) -> the answer is 11 (which mod 10 = 1) </pre> <p>I am interested in minimizing the maximal total time spent on a sequence of <code>n</code> such operations. It is obviously possible to just maintain a list of elements for <code>S</code> and iterate through them for every <code>minmod</code> operation; then insert is <code>O(1)</code> and minmod is <code>O(|S|)</code>, which would take <code>O(n^2)</code> time for <code>n</code> operations (e.g., <code>n/2</code> <code>insert</code> operations followed by <code>n/2</code> <code>minmod</code> operations would take roughly <code>n^2/4</code> operations).</p> <p>So: is it possible to do better than <code>O(n^2)</code> for a sequence of <code>n</code> operations? Maybe <code>O(n sqrt(n))</code> or <code>O(n log(n))</code>? If this is possible, then I would also be interested to know if there are data structures that additionally admit removing single elements from <code>S</code>, or removing all numbers within an interval.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload