Fast algorithm for pandigital check
<p>I'm working on a project for which I need a very fast algorithm for checking whether a supplied number is pandigital. Though the logic seems sound, I'm not particularly happy with performance of the methods described below. </p>

<p>I can check up to one million 9-digit numbers in about 520ms, 600ms and 1600ms respectively. I'm working on a low-latency application and in production I'll have a dataset of about 9 or 9.5 billion 7- to 9-digit numbers that I'll need to check. </p>

<p>I have three candidiates right now (well, really two) that use the following logic:</p>

<p><strong>Method 1:</strong> I take an input <code>N</code>, split into into a byte array of its constituent digits, sort it using an <code>Array.Sort</code> function and iterate over the array using a <code>for</code> loop checking for element vs counter consistency:</p>

<pre><code> byte[] Digits = SplitDigits(N);
 int len = NumberLength(N);
 Array.Sort(Digits);
 for (int i = 0; i &lt;= len - 1; i++)
 {
     if (i + 1 != Digits[i])
          return false;
 }
</code></pre>

<p><strong>Method 2:</strong> This method is based on a bit of dubious logic, but I split the input <code>N</code> into a byte array of constituent digits and then make the following test:</p>

<pre><code> if (N * (N + 1) * 0.5 == DigitSum(N) &amp;&amp; Factorial(len) == DigitProduct(N))
      return true;
</code></pre>

<p><strong>Method 3:</strong> I dislike this method, so not a real candidate but I cast the int to a string and then use <code>String.Contains</code> to determine if the required string is pandigital.</p>

<p>The second and third method have fairly stable runtimes, though the first method bounces around a lot - it can go as high as 620ms at times.</p>

<p>So ideally I really like to reduce the runtime for the million 9-digit mark to under 10ms. Any thoughts?</p>

<p>I'm running this on a Pentium 6100 laptop at 2GHz. </p>

<p>PS - is the mathematical logic of the second method sound?</p>
