StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'm assuming you want a solution where the numbers are in a range, and you have the starting and ending number. Imagine starting with the start number and counting up until you reach the end number - it would work, but it would be slow. I think the trick to a fast algorithm is to realize that in order to go up one digit in the 10^x place and keep everything else the same, you need to use all of the digits before it 10^x times plus all digits 0-9 10^(x-1) times. (Except that your counting may have involved a carry past the x-th digit - I correct for this below.)</p> <p>Here's an example. Say you're counting from 523 to 1004.</p> <ul> <li>First, you count from 523 to 524. This uses the digits 5, 2, and 4 once each.</li> <li>Second, count from 524 to 604. The rightmost digit does 6 cycles through all of the digits, so you need 6 copies of each digit. The second digit goes through digits 2 through 0, 10 times each. The third digit is 6 5 times and 5 100-24 times.</li> <li>Third, count from 604 to 1004. The rightmost digit does 40 cycles, so add 40 copies of each digit. The second from right digit doers 4 cycles, so add 4 copies of each digit. The leftmost digit does 100 each of 7, 8, and 9, plus 5 of 0 and 100 - 5 of 6. The last digit is 1 5 times.</li> </ul> <p>To speed up the last bit, look at the part about the rightmost two places. It uses each digit 10 + 1 times. In general, 1 + 10 + ... + 10^n = (10^(n+1) - 1)/9, which we can use to speed up counting even more.</p> <p>My algorithm is to count up from the start number to the end number (using base-10 counting), but use the fact above to do it quickly. You iterate through the digits of the starting number from least to most significant, and at each place you count up so that that digit is the same as the one in the ending number. At each point, n is the number of up-counts you need to do before you get to a carry, and m the number you need to do afterwards.</p> <p>Now let's assume pseudocode counts as a language. Here, then, is what I would do:</p> <pre> convert start and end numbers to digit arrays start[] and end[] create an array counts[] with 10 elements which stores the number of copies of each digit that you need iterate through start number from right to left. at the i-th digit, let d be the number of digits you must count up to get from this digit to the i-th digit in the ending number. (i.e. subtract the equivalent digits mod 10) add d * (10^i - 1)/9 to each entry in count. let m be the numerical value of all the digits to the right of this digit, n be 10^i - m. for each digit e from the left of the starting number up to and including the i-th digit, add n to the count for that digit. for j in 1 to d increment the i-th digit by one, including doing any carries for each digit e from the left of the starting number up to and including the i-th digit, add 10^i to the count for that digit for each digit e from the left of the starting number up to and including the i-th digit, add m to the count for that digit. set the i-th digit of the starting number to be the i-th digit of the ending number. </pre> <p>Oh, and since the value of i increases by one each time, keep track of your old 10^i and just multiply it by 10 to get the new one, instead of exponentiating each time.</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