4

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.

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.

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

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

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

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

 if (N * (N + 1) * 0.5 == DigitSum(N) && Factorial(len) == DigitProduct(N))
      return true;

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

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.

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

I'm running this on a Pentium 6100 laptop at 2GHz.

PS - is the mathematical logic of the second method sound?

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
insomniac
  • 192
  • 1
  • 3
  • 16
  • Somehow, this is already answered [here](http://stackoverflow.com/questions/2484892/fastest-algorithm-to-check-if-a-number-is-pandigital) – Patrick Quirk Mar 03 '13 at 18:45
  • No the second method isn't valid, because for a start, there are multiple ways to sum to N(N+1)/2. – Oliver Charlesworth Mar 03 '13 at 18:46
  • Note that in all three cases, the common procedure is converting the integer into its decimal digits. So unless that component is substantially lower than your 10ms target, it doesn't really matter which method you choose! – Oliver Charlesworth Mar 03 '13 at 18:48
  • Yes, agreed. Which is why I'm checking for both N(N+1)/2 **and** Factorial(N). I would have thought this method is valid? – insomniac Mar 03 '13 at 18:55
  • Another point to consider that 1 million 4-byte integers in 10ms is an effective input rate of 400MB/s. If your data is coming from disk or network, then that's likely to be the bottleneck. – Oliver Charlesworth Mar 03 '13 at 18:57
  • Ok, I have no idea whether that will work in all cases! (A crude way to check is simply to iterate over all possible inputs (it should only take a few seconds)). – Oliver Charlesworth Mar 03 '13 at 18:58

2 Answers2

1

Method 1

Pre-compute a sorted list of the 362880 9-digit pandigital numbers. This will take only a few milliseconds. Then for each request, first check if the number is divisible by 9: It must be to be pandigital. If it is, then use a binary search to check if it is in your pre-computed list.

Method 2

Again, check if the number is divisible by 9. Then use a bit vector to track the presence of digits. Also use modular multiplication to replace the division by a multiplication.

static bool IsPandigital(int n)
{
    if (n != 9 * (int)((0x1c71c71dL * n) >> 32))
        return false;

    int flags = 0;
    while (n > 0) {
        int q = (int)((0x1999999aL * n) >> 32);
        flags |= 1 << (n - q * 10);
        n = q;
    }
    return flags == 0x3fe;
}

Method 1 comes in at 15ms/1M. Method 2 comes in at 5.5ms/1M on my machine. This is C# compiled to x64 on an i7 950.

Jeffrey Sax
  • 10,253
  • 3
  • 29
  • 40
0

just a thought: (after the definitition of pandigital from wikipedia)

int n = 1234567890;
int Flags = 0;
int Base = 10;
while(n != 0)
{
    Flags |= 1<<(n % Base); n /= Base;
}
bool bPanDigital = Flags == ((1 << Base) - 1);
user287107
  • 9,286
  • 1
  • 31
  • 47