StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow to calculate the digit products of the consecutive numbers efficiently?
text
Body
copied!<p>I'm trying to calculate the product of digits of each number of a sequence of numbers, for example: </p> <blockquote> <p>21, 22, 23 ... 98, 99 .. </p> </blockquote> <p>would be:</p> <blockquote> <p>2, 4, 6 ... 72, 81 .. </p> </blockquote> <p>To reduce the complexity, I would consider only the [<a href="http://simple.wikipedia.org/wiki/Consecutive_integer" rel="noreferrer">consecutive numbers</a>] in a limited length of digits, such as from <code>001</code> to <code>999</code> or from <code>0001</code> to <code>9999</code>. </p> <p>However, when the sequence is large, for example, <code>1000000000</code>, repeatedly <em>extract the digits and then multiply</em> for every number would be inefficient. </p> <p>The basic idea is to skip the consecutive zeros we will encounter during the calculation, something like: </p> <pre><code>using System.Collections.Generic; using System.Linq; using System; // note the digit product is not given with the iteration // we would need to provide a delegate for the calculation public static partial class NumericExtensions { public static void NumberIteration( this int value, Action<int, int[]> delg, int radix=10) { var digits=DigitIterator(value, radix).ToArray(); var last=digits.Length-1; var emptyArray=new int[] { }; var pow=(Func<int, int, int>)((x, y) => (int)Math.Pow(x, 1+y)); var weights=Enumerable.Repeat(radix, last-1).Select(pow).ToArray(); for(int complement=radix-1, i=value, j=i; i>0; i-=1) if(i>j) delg(i, emptyArray); else if(0==digits[0]) { delg(i, emptyArray); var k=0; for(; k<last&&0==digits[k]; k+=1) ; var y=(digits[k]-=1); if(last==k||0!=y) { if(0==y) { // implied last==k digits=new int[last]; last-=1; } for(; k-->0; digits[k]=complement) ; } else { j=i-weights[k-1]; } } else { // receives digits of a number which doesn't contain zeros delg(i, digits); digits[0]-=1; } delg(0, emptyArray); } static IEnumerable<int> DigitIterator(int value, int radix) { if(-2<radix&&radix<2) radix=radix<0?-2:2; for(int remainder; 0!=value; ) { value=Math.DivRem(value, radix, out remainder); yield return remainder; } } } </code></pre> <p>This is only for the enumeration of numbers, to avoid numbers which contain zeros to be calculated in the first place, the digit products are not yet given by the code; but generate the digit products by providing a delegate to perform the calculation will still take time. </p> <p>How to calculate the digit products of the consecutive numbers efficiently?</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