StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The naive approach would be a tree-recursive algorithm.</p> <p>Our recursive method would slowly build the number up, e.g. it would start at <code>xxxxxx</code>, return the sum of a call with <code>1xxxxx</code> and <code>0xxxxx</code>, which themselves will return the sum of a call with <code>10</code>, <code>11</code> and <code>00</code>, <code>01</code>, etc. except if the x/y conditions are NOT satisfied for the string it would build by calling itself it does NOT go down that path, and if you are at a terminal condition (built a number of the correct length) you return 1. (note that since we're building the string up from left to right, you don't have to check x/y for the entire string, just also considering the newly added digit!)</p> <p>By returning a sum over all calls then all of the returned 1s will pool together and be returned by the initial call, equalling the number of constructed strings.</p> <p>No idea what the big O notation for time complexity is for this one, it could be as bad as <code>O(2^n)*O(checking x/y conditions)</code> but it will prune lots of branches off the tree in most cases.</p> <p><strong>UPDATE:</strong> One insight I had is that all branches of the recursive tree can be 'merged' if they have identical last <code>x</code> digits so far, because then the same checks would be applied to all digits hereafter so you may as well double them up and save a lot of work. This now requires building the tree explicitly instead of implicitly via recursive calls, and maybe some kind of hashing scheme to detect when branches have identical <code>x</code> endings, but for large length it would provide a huge speedup.</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