Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This may be done by converting the input array to the list of counters "in-place" in O(N) time. Of course this assumes input array is not immutable. There is no need for any additional assumptions about unused bits in each array element.</p> <p>Start with the following pre-processing: try to move each array's element to the position determined by element's value; move element on this position also to the position determined by its value; continue until:</p> <ul> <li>next element is moved to the position from where this cycle was started,</li> <li>next element cannot be moved because it is already on the position corresponding to its value (in this case put current element to the position from where this cycle was started).</li> </ul> <p>After pre-processing every element either is located at its "proper" position or "points" to its "proper" position. In case we have an unused bit in each element, we could convert each properly positioned element into a counter, initialize it with "1", and allow each "pointing" element to increase appropriate counter. Additional bit allows to distinguish counters from values. The same thing may be done without any additional bits but with less trivial algorithm.</p> <p>Count how may values in the array are equal to 0 or 1. If there are any such values, reset them to zero and update counters at positions 0 and/or 1. Set <code>k=2</code> (size of the array's part that has values less than <code>k</code> replaced by counters). Apply the following procedure for k = 2, 4, 8, ...</p> <ol> <li>Find elements at positions <code>k .. 2k-1</code> which are at their "proper" position, replace them with counters, initial value is "1".</li> <li>For any element at positions <code>k .. 2k-1</code> with values <code>2 .. k-1</code> update corresponding counter at positions <code>2 .. k-1</code> and reset value to zero.</li> <li>For any element at positions <code>0 .. 2k-1</code> with values <code>k .. 2k-1</code> update corresponding counter at positions <code>k .. 2k-1</code> and reset value to zero.</li> </ol> <p>All iterations of this procedure together have O(N) time complexity. At the end the input array is completely converted to the array of counters. The only difficulty here is that up to two counters at positions <code>0 .. 2k-1</code> may have values greater than <code>k-1</code>. But this could be mitigated by storing two additional indexes for each of them and processing elements at these indexes as counters instead of values.</p> <p>After an array of counters is produced, we could just multiply pairs of counters (where corresponding pair of indexes sum to <code>X</code>) to get the required counts of pairs.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind pairs that sum to X in an array of integers of size N having element in the range 0 to N-1
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USEvgeny Kluev
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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