StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>So in a break with my normal tradition of not posting algorithms I don't have a proof for, I think I should mention that there's an algorithm that appears to be correct for numbers up to 50,000+ and runs in O(log n) time. This is due to <a href="https://twitter.com/sophiawestwood" rel="nofollow">Sophia Westwood</a>, who I worked on this problem with for about three hours today. All credit for this is due to her. Empirically it seems to work beautifully, and it's much, much faster than the O(n) solutions.</p> <p>One observation about the structure of this problem is that if n is sufficiently large (n ≥ 5), then if you put a 1 anywhere, the problem splits into two subproblems, one to the left of the 1 and one to the right. Although the 1s might be placed in the different halves at different times, the eventual placement is the same as if you solved each half separately and combined them back together.</p> <p>The next observation is this: suppose you have an array of size 2<sup>k</sup> + 1 for some k. In that case, suppose that you put a 1 on either side of the array. Then:</p> <ul> <li>The next 1 is placed on the other side of the array.</li> <li>The next 1 is placed in the middle.</li> <li>You now have two smaller subproblems of size 2<sup>k-1</sup> + 1.</li> </ul> <p>The important part about this is that the resulting bit pattern is an alternating series of 1s and 0s. For example:</p> <ul> <li>For 5 = 4 + 1, we get 10101</li> <li>For 9 = 8 + 1, we get 101010101</li> <li>For 17 = 16 + 1, we get 10101010101010101</li> </ul> <p>The reason this matters is the following: suppose you have n total elements in the array and let k be the largest possible value for which 2<sup>k</sup> + 1 ≤ n. If you place the 1 at position 2<sup>k</sup> + 1, then the left part of the array up to that position will end up getting tiled with alternating 1s and 0s, which puts a <em>lot</em> of 1s into the array.</p> <p>What's not obvious is that placing the 1 bit there, for all numbers up to 50,000, appears to yield an optimal solution! I've written a Python script that checks this (using a recurrence relation similar to the one @justhalf) and it seems to work well. The reason that this fact is so useful is that it's really easy to compute this index. In particular, if 2<sup>k</sup> + 1 ≤ n, then 2<sup>k</sup> ≤ n - 1, so k ≤ lg (n - 1). Choosing the value &lfloor;lg (n - 1) &rfloor; as your choice of k then lets you compute the bit index by computing 2<sup>k</sup> + 1. This value of k can be computed in O(log n) time and the exponentiation can be done in O(log n) time as well, so the total runtime is Θ(log n).</p> <p>The only issue is that I haven't formally proven that this works. All I know is that it's right for the first 50,000 values we've tried. :-)</p> <p>Hope this helps!</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