Fastest algorithm to check if a number is pandigital?

Question

Pandigital number is a number that contains the digits 1..number length.
For example 123, 4312 and 967412385.

I have solved many Project Euler problems, but the Pandigital problems always exceed the one minute rule.

This is my pandigital function:

private boolean isPandigital(int n){
    Set<Character> set= new TreeSet<Character>();   
    String string = n+"";
    for (char c:string.toCharArray()){
        if (c=='0') return false;
        set.add(c);
    }
    return set.size()==string.length();
}

Create your own function and test it with this method

int pans=0;
for (int i=123456789;i<=123987654;i++){
    if (isPandigital(i)){
         pans++;
    }
}

Using this loop, you should get 720 pandigital numbers. My average time was 500 millisecond.

I'm using Java, but the question is open to any language.

UPDATE
@andras answer has the best time so far, but @Sani Huttunen answer inspired me to add a new algorithm, which gets almost the same time as @andras.

Solution 1

C#, 17ms, if you really want a check.

class Program
{
    static bool IsPandigital(int n)
    {
        int digits = 0; int count = 0; int tmp;

        for (; n > 0; n /= 10, ++count)
        {
            if ((tmp = digits) == (digits |= 1 << (n - ((n / 10) * 10) - 1)))
                return false;
        }

        return digits == (1 << count) - 1;
    }

    static void Main()
    {
        int pans = 0;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 123456789; i <= 123987654; i++)
        {
            if (IsPandigital(i))
            {
                pans++;
            }
        }
        sw.Stop();
        Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds);
        Console.ReadKey();
    }
}

For a check that is consistent with the Wikipedia definition in base 10:

const int min = 1023456789;
const int expected = 1023;

static bool IsPandigital(int n)
{
    if (n >= min)
    {
        int digits = 0;

        for (; n > 0; n /= 10)
        {
            digits |= 1 << (n - ((n / 10) * 10));
        }

        return digits == expected;
    }
    return false;
}

---

To enumerate numbers in the range you have given, generating permutations would suffice.

The following is not an answer to your question in the strict sense, since it does not implement a check. It uses a generic permutation implementation not optimized for this special case - it still generates the required 720 permutations in 13ms (line breaks might be messed up):

static partial class Permutation
{
    /// <summary>
    /// Generates permutations.
    /// </summary>
    /// <typeparam name="T">Type of items to permute.</typeparam>
    /// <param name="items">Array of items. Will not be modified.</param>
    /// <param name="comparer">Optional comparer to use.
    /// If a <paramref name="comparer"/> is supplied, 
    /// permutations will be ordered according to the 
    /// <paramref name="comparer"/>
    /// </param>
    /// <returns>Permutations of input items.</returns>
    public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items, IComparer<T> comparer)
    {
        int length = items.Length;
        IntPair[] transform = new IntPair[length];
        if (comparer == null)
        {
            //No comparer. Start with an identity transform.
            for (int i = 0; i < length; i++)
            {
                transform[i] = new IntPair(i, i);
            };
        }
        else
        {
            //Figure out where we are in the sequence of all permutations
            int[] initialorder = new int[length];
            for (int i = 0; i < length; i++)
            {
                initialorder[i] = i;
            }
            Array.Sort(initialorder, delegate(int x, int y)
            {
                return comparer.Compare(items[x], items[y]);
            });
            for (int i = 0; i < length; i++)
            {
                transform[i] = new IntPair(initialorder[i], i);
            }
            //Handle duplicates
            for (int i = 1; i < length; i++)
            {
                if (comparer.Compare(
                    items[transform[i - 1].Second], 
                    items[transform[i].Second]) == 0)
                {
                    transform[i].First = transform[i - 1].First;
                }
            }
        }

        yield return ApplyTransform(items, transform);

        while (true)
        {
            //Ref: E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997
            //Find the largest partition from the back that is in decreasing (non-icreasing) order
            int decreasingpart = length - 2;
            for (;decreasingpart >= 0 && 
                transform[decreasingpart].First >= transform[decreasingpart + 1].First;
                --decreasingpart) ;
            //The whole sequence is in decreasing order, finished
            if (decreasingpart < 0) yield break;
            //Find the smallest element in the decreasing partition that is 
            //greater than (or equal to) the item in front of the decreasing partition
            int greater = length - 1;
            for (;greater > decreasingpart && 
                transform[decreasingpart].First >= transform[greater].First; 
                greater--) ;
            //Swap the two
            Swap(ref transform[decreasingpart], ref transform[greater]);
            //Reverse the decreasing partition
            Array.Reverse(transform, decreasingpart + 1, length - decreasingpart - 1);
            yield return ApplyTransform(items, transform);
        }
    }

    #region Overloads

    public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items)
    {
        return Permute(items, null);
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items, IComparer<T> comparer)
    {
        List<T> list = new List<T>(items);
        return Permute(list.ToArray(), comparer);
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items)
    {
        return Permute(items, null);
    }

    #endregion Overloads

    #region Utility

    public static IEnumerable<T> ApplyTransform<T>(
        T[] items, 
        IntPair[] transform)
    {
        for (int i = 0; i < transform.Length; i++)
        {
            yield return items[transform[i].Second];
        }
    }

    public static void Swap<T>(ref T x, ref T y)
    {
        T tmp = x;
        x = y;
        y = tmp;
    }

    public struct IntPair
    {
        public IntPair(int first, int second)
        {
            this.First = first;
            this.Second = second;
        }
        public int First;
        public int Second;
    }

    #endregion
}

class Program
{

    static void Main()
    {
        int pans = 0;
        int[] digits = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Stopwatch sw = new Stopwatch();
        sw.Start();
        foreach (var p in Permutation.Permute(digits))
        {
            pans++;
            if (pans == 720) break;
        }
        sw.Stop();
        Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds);
        Console.ReadKey();
    }
}

Solution 2

This is my solution:

static char[][] pandigits = new char[][]{
        "1".toCharArray(),
        "12".toCharArray(),
        "123".toCharArray(),
        "1234".toCharArray(),
        "12345".toCharArray(),
        "123456".toCharArray(),
        "1234567".toCharArray(),
        "12345678".toCharArray(),
        "123456789".toCharArray(),
};
private static boolean isPandigital(int i)
{
    char[] c = String.valueOf(i).toCharArray();
    Arrays.sort(c);
    return Arrays.equals(c, pandigits[c.length-1]);
}

Runs the loop in 0.3 seconds on my (rather slow) system.

Solution 3

Using a bit vector to keep track of which digits have been found appears to be the fastest raw method. There are two ways to improve it:

1. Check if the number is divisible by 9. This is a necessary condition for being pandigital, so we can exclude 88% of numbers up front.

2. Use multiplication and shifts instead of divisions, in case your compiler doesn't do that for you.

This gives the following, which runs the test benchmark in about 3ms on my machine. It correctly identifies the 362880 9-digit pan-digital numbers between 100000000 and 999999999.

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;
}

Solution 4

Two things you can improve:

• You don't need to use a set: you can use a boolean array with 10 elements
• Instead of converting to a string, use division and the modulo operation (%) to extract the digits.

Solution 5

My solution involves Sums and Products. This is in C# and runs in about 180ms on my laptop:

static int[] sums = new int[] {1, 3, 6, 10, 15, 21, 28, 36, 45};
static int[] products = new int[] {1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

static void Main(string[] args)
{
  var pans = 0;
  for (var i = 123456789; i <= 123987654; i++)
  {
    var num = i.ToString();
    if (Sum(num) == sums[num.Length - 1] && Product(num) == products[num.Length - 1])
      pans++;
  }
  Console.WriteLine(pans);
}

protected static int Sum(string num)
{
  int sum = 0;
  foreach (char c in num)
    sum += (int) (c - '0');

  return sum;
}

protected static int Product(string num)
{
  int prod = 1;
  foreach (char c in num)
    prod *= (int)(c - '0');

  return prod;
}

View more solutions

Comments

[Admin]

The trick with the first point is to keep track of the highest and lowest flags set. If you try to set the same flag twice, you have a duplicate - otherwise you want min=1 and max=expected_max at the end.

[Chris Dennett]

if (!set.add(c)) return false; < smaller :)

[Reed Copsey]

@Chris: Yes, but identical post compilation ;)

[Tyler]

Great idea but I think there's some quirks in the code. See my answer: stackoverflow.com/questions/2484892/…

[mohdajami]

I have tried your algorithm, in Java its taking around 35ms, im very impressed :)

[mohdajami]

@Sameer, can you please add the times for each algorithm in milliseconds?

[Andras Vass]

@medopal: thank you. :) I have updated it meanwhile. Could you please give it a try in Java?

[mohdajami]

@andras, wow, it dropped half the time, its getting 20ms in Java, good work :)

[Andras Vass]

@medopal: thanks, your comment about modulo in Java made me think. :) (In particular, to avoid it in many cases - in C# it did not make much difference using the div/mul hack on my AMD, so I hadn't bothered for the first time.)

[mohdajami]

my calculations were made on a Macbook, with Java 5. My PC takes a little more time. I don't think we can reach anything less than that, should be called "andras pandigital algorithm" :)

[Andras Vass]

@medopal: thanks. It is an honor, Sir. xD (For checking, it does a pretty good job, I believe. I should add that for generating these numbers, you should really choose the permutation method as pointed out in the comments.)

[Charles]

Why divide by 10 twice if that's the slow part of the code? Try int nn = n / 10; digit = n - 10 * nn; n = nn;.

[Handcraftsman]

@Charles, I tried pulling the n/10 out to a variable both inside and outside the do..while but it didn't make a significant speed difference on my machine.

[Charles]

Interesting that replacing % with / helped but halving the number of / did not -- unless perhaps the IL only emitted one / in the first place?

[mohdajami]

I'm impressed :). I will try that in Java and report back.

[Jeffrey Sax]

@Moberg It multiplies by 2^32/9 (using 64 bit arithmetic) and then shifts by 32 bits.

[Stefan Gruenwald]

Good idea, but the task on Project Euler was to find all the permutation of length 41 (10**40 number) that is pandigital and is also a step number (each digit is either +1 or -1 to the previous, except 9 (-1 only) and 0 (+1 only)). So not just pandigital.

[schirrmacher]

"if ((tmp = digits) == (digits |= 1 << (n - ((n / 10) * 10) - 1)))" is a little bit confusing ;) why didn't you split that?! but very nice solution!