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.

Answer 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();     } } 

Answer 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.

Answer 3

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.