Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here is an algorithm that is <code>O(n + size(smallest subset) * log(n))</code>. If the smallest subset is much smaller than the array, this will be <code>O(n)</code>.</p> <p>Read <a href="http://en.wikipedia.org/wiki/Heap_%28data_structure%29" rel="nofollow">http://en.wikipedia.org/wiki/Heap_%28data_structure%29</a> if my description of the algorithm is unclear (it is light on details, but the details are all there).</p> <ol> <li>Turn the array into a heap arranged such that the biggest element is available in time <code>O(n)</code>.</li> <li>Repeatedly extract the biggest element from the heap until their sum is large enough. This takes <code>O(size(smallest subset) * log(n))</code>.</li> </ol> <p>This is almost certainly the answer they were hoping for, though not getting it shouldn't be a deal breaker.</p> <p><em>Edit:</em> Here is another variant that is often faster, but can be slower.</p> <pre><code>Walk through elements, until the sum of the first few exceeds S. Store current_sum. Copy those elements into an array. Heapify that array such that the minimum is easy to find, remember the minimum. For each remaining element in the main array: if min(in our heap) &lt; element: insert element into heap increase current_sum by element while S + min(in our heap) &lt; current_sum: current_sum -= min(in our heap) remove min from heap </code></pre> <p>If we get to reject most of the array without manipulating our heap, this can be up to twice as fast as the previous solution. But it is also possible to be slower, such as when the last element in the array happens to be bigger than S.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind the minimum number of elements required so that their sum equals or exceeds S
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USbtilly
    1. USbtilly
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFind the minimum number of elements required so that their sum equals or exceeds S
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis is O(n + K log n) (and not O(n + K log K) as you claim), isn't it? +1 though. This is definitely the best answer so far.
      singulars
      1. PO
      1. This table or related slice is empty.
    2. CO@Moron: Oops, you're right. I had another one before that could hit the lower bound, but realized that it would usually be worse. I'll add that solution later.
      singulars
      1. PO
      1. USbtilly
    3. CO@Moron: Second solution added.
      singulars
      1. PO
      1. USbtilly
 

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