Q: Fastest algorithm to check if a number is pandigital? 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.

A: 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.


A: 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:


*

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

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


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


A: 
Why find when you can make them?

from itertools import *

def generate_pandigital(length):
    return (''.join for each in list(permutations('123456789',length)))

def test():
    for i in range(10):
        print i
        generate_pandigital(i)

if __name__=='__main__':
    test()


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


A: J does this nicely:

    isPandigital =: 3 : 0
        *./ (' ' -.~ ": 1 + i. # s) e. s =. ": y
    )

    isPandigital"0 (123456789 + i. 1 + 123987654 - 123456789)

But slowly. I will revise. For now, clocking at 4.8 seconds.
EDIT:
If it's just between the two set numbers, 123456789 and 123987654, then this expression:

    *./"1 (1+i.9) e."1 (9#10) #: (123456789 + i. 1 + 123987654 - 123456789)

Runs in 0.23 seconds. It's about as fast, brute-force style, as it gets in J.

A: TheMachineCharmer is right. At least for some the problems, it's better to iterate over all the pandigitals, checking each one to see if it fits the criteria of the problem. However, I think their code is not quite right.
I'm not sure which is better SO etiquette in this case: Posting a new answer or editing theirs. In any case, here is the modified Python code which I believe to be correct, although it doesn't generate 0-to-n pandigitals.
from itertools import *

def generate_pandigital(length):
    'Generate all 1-to-length pandigitals'
    return (''.join(each) for each in list(permutations('123456789'[:length])))

def test():
    for i in range(10):
        print 'Generating all %d-digit pandigitals' % i
        for (n,p) in enumerate(generate_pandigital(i)):
            print n,p

if __name__=='__main__':
    test()


A: 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.

A: You could add:
 if (set.add(c)==false) return false;

This would short circuit a lot of your computations, since it'll return false as soon as a duplicate was found, since add() returns false in this case.

A: bool IsPandigital (unsigned long n) {
  if (n <= 987654321) {
      hash_map<int, int> m;
      unsigned long count = (unsigned long)(log((double)n)/log(10.0))+1;

      while (n) {
          ++m[n%10];
          n /= 10;
      }

      while (m[count]==1 && --count);

      return !count;
  }

  return false;
}

bool IsPandigital2 (unsigned long d) {
  // Avoid integer overflow below if this function is passed a very long number
  if (d <= 987654321) {
      unsigned long sum = 0;
      unsigned long prod = 1;
      unsigned long n = d;

      unsigned long max = (log((double)n)/log(10.0))+1;
      unsigned long max_sum = max*(max+1)/2;
      unsigned long max_prod = 1;

      while (n) {
          sum += n % 10;
          prod *= (n%10);
          max_prod *= max;
          --max;
          n /= 10;
      }

      return (sum == max_sum) && (prod == max_prod);
  }


A: I have a solution for generating Pandigital numbers using StringBuffers in Java. On my laptop, my code takes a total of 5ms to run. Of this only 1ms is required for generating the permutations using StringBuffers; the remaining 4ms are required for converting this StringBuffer to an int[]. 
@medopal: Can you check the time this code takes on your system?
public class GenPandigits 
{

 /**
 * The prefix that must be appended to every number, like 123.
 */
int prefix;

/**
 * Length in characters of the prefix.
 */
int plen;

/**
 * The digit from which to start the permutations
 */
String beg;

/**
 * The length of the required Pandigital numbers.
 */
int len;

/**
 * @param prefix If there is no prefix then this must be null
 * @param beg If there is no prefix then this must be "1"
 * @param len Length of the required numbers (excluding the prefix)
 */
public GenPandigits(String prefix, String beg, int len)
{
    if (prefix == null) 
    {
        this.prefix = 0;
        this.plen = 0;
    }
    else 
    {
        this.prefix = Integer.parseInt(prefix);
        this.plen = prefix.length();
    }
    this.beg = beg;
    this.len = len;
}
public StringBuffer genPermsBet()
{
    StringBuffer b = new StringBuffer(beg);
    for(int k=2;k<=len;k++)
    {
        StringBuffer rs = new StringBuffer();
        int l = b.length();
        int s = l/(k-1);
        String is = String.valueOf(k+plen);
        for(int j=0;j<k;j++)
        {
            rs.append(b);
            for(int i=0;i<s;i++)
            {
                rs.insert((l+s)*j+i*k+j, is);
            }
        }
        b = rs;
    }
    return b;
}

public int[] getPandigits(String buffer)
{
    int[] pd = new int[buffer.length()/len];
    int c= prefix;
    for(int i=0;i<len;i++)
        c =c *10;
    for(int i=0;i<pd.length;i++)
        pd[i] = Integer.parseInt(buffer.substring(i*len, (i+1)*len))+c;
    return pd;
}
public static void main(String[] args) 
{
    GenPandigits gp = new GenPandigits("123", "4", 6);

    //GenPandigits gp = new GenPandigits(null, "1", 6);

    long beg = System.currentTimeMillis();
    StringBuffer pansstr = gp.genPermsBet();
    long end = System.currentTimeMillis();
    System.out.println("Time = " + (end - beg));
    int pd[] = gp.getPandigits(pansstr.toString());
    long end1 = System.currentTimeMillis();
    System.out.println("Time = " + (end1 - end));
    }
}

This code can also be used for generating all Pandigital numbers(excluding zero). Just change the object creation call to 
GenPandigits gp = new GenPandigits(null, "1", 9);

This means that there is no prefix, and the permutations must start from "1" and continue till the length of the numbers is 9.
Following are the time measurements for different lengths.

@andras: Can you try and run your code to generate the nine digit Pandigital numbers? What time does it take?

A: This c# implementation is about 8% faster than @andras over the range 123456789 to 123987654 but it is really difficult to see on my test box as his runs in 14ms and this one runs in 13ms.
static bool IsPandigital(int n)
{
    int count = 0;
    int digits = 0;
    int digit;
    int bit;
    do
    {
        digit = n % 10;
        if (digit == 0)
        {
            return false;
        }
        bit = 1 << digit;

        if (digits == (digits |= bit))
        {
            return false;
        }

        count++;
        n /= 10;
    } while (n > 0);
    return (1<<count)-1 == digits>>1;
}

If we average the results of 100 runs we can get a decimal point.
public void Test()
{
    int pans = 0;
    var sw = new Stopwatch();
    sw.Start();
    for (int count = 0; count < 100; count++)
    {
        pans = 0;
        for (int i = 123456789; i <= 123987654; i++)
        {
            if (IsPandigital(i))
            {
                pans++;
            }
        }
    }
    sw.Stop();
    Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds / 100m);
}

@andras implementation averages 14.4ms and this implementation averages 13.2ms
EDIT: 
It seems that mod (%) is expensive in c#.  If we replace the use of the mod operator with a hand coded version then this implementation averages 11ms over 100 runs.
private static bool IsPandigital(int n)
{
    int count = 0;
    int digits = 0;
    int digit;
    int bit;
    do
    {
        digit = n - ((n / 10) * 10);
        if (digit == 0)
        {
            return false;
        }
        bit = 1 << digit;

        if (digits == (digits |= bit))
        {
            return false;
        }

        count++;
        n /= 10;
    } while (n > 0);
    return (1 << count) - 1 == digits >> 1;
}

EDIT: Integrated n/=10 into the digit calculation for a small speed improvement.
private static bool IsPandigital(int n)
{
    int count = 0;
    int digits = 0;
    int digit;
    int bit;
    do
    {
        digit = n - ((n /= 10) * 10);
        if (digit == 0)
        {
            return false;
        }
        bit = 1 << digit;

        if (digits == (digits |= bit))
        {
            return false;
        }

        count++;
    } while (n > 0);
    return (1 << count) - 1 == digits >> 1;
}


A: #include <cstdio>
#include <ctime>

bool isPandigital(long num)
{
  int arr [] = {1,2,3,4,5,6,7,8,9}, G, count = 9;
  do
  {
    G = num%10;
    if (arr[G-1])
      --count;
    arr[G-1] = 0;
  } while (num/=10);

  return (!count);
}

int main()
{
  clock_t start(clock());

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

  double end((double)(clock() - start));

  printf("\n\tFound %d Pandigital numbers in %lf seconds\n\n", pans, end/CLOCKS_PER_SEC);

  return 0;
}

Simple implementation. Brute-forced and computes in about 140 ms

A: In Java
You can always just generate them, and convert the Strings to Integers, which is faster for larger numbers
public static List<String> permutation(String str) {
    List<String> permutations = new LinkedList<String>();
    permutation("", str, permutations);
    return permutations;
}

private static void permutation(String prefix, String str, List<String> permutations) {
    int n = str.length();
    if (n == 0) {
        permutations.add(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i),
                    str.substring(0, i) + str.substring(i + 1, n), permutations);
        }
    }
}

The below code works for testing a numbers pandigitality.
For your test mine ran in around ~50ms
1-9 PanDigital
public static boolean is1To9PanDigit(int i) {
    if (i < 1e8) {
        return false;
    }
    BitSet set = new BitSet();
    while (i > 0) {
        int mod = i % 10;
        if (mod == 0 || set.get(mod)) {
            return false;
        }
        set.set(mod);
        i /= 10;
    }
    return true;
}

or more general, 1 to N,
public static boolean is1ToNPanDigit(int i, int n) {
    BitSet set = new BitSet();
    while (i > 0) {
        int mod = i % 10;
        if (mod == 0 || mod > n || set.get(mod)) {
            return false;
        }
        set.set(mod);
        i /= 10;
    }
    return set.cardinality() == n;
}

And just for fun, 0 to 9, zero requires extra logic due to a leading zero
public static boolean is0To9PanDigit(long i) {
    if (i < 1e6) {
        return false;
    }
    BitSet set = new BitSet();
    if (i <= 123456789) { // count for leading zero
        set.set(0);
    }
    while (i > 0) {
        int mod = (int) (i % 10);
        if (set.get(mod)) {
            return false;
        }
        set.set(mod);
        i /= 10;
    }
    return true;
}

Also for setting iteration bounds:
public static int maxPanDigit(int n) {
    StringBuffer sb = new StringBuffer();
    for(int i = n; i > 0; i--) {
        sb.append(i);
    }
    return Integer.parseInt(sb.toString());
}

public static int minPanDigit(int n) {
    StringBuffer sb = new StringBuffer();
    for(int i = 1; i <= n; i++) {
        sb.append(i);
    }
    return Integer.parseInt(sb.toString());
}

You could easily use this code to generate a generic MtoNPanDigital number checker

A: I decided to use something like this:

  def is_pandigital(n, zero_full=True, base=10):
    """Returns True or False if the number n is pandigital.

    This function returns True for formal pandigital numbers as well as
    n-pandigital
    """
    r, l = 0, 0
    while n:
        l, r, n = l + 1, r + n % base, n / base
    t = xrange(zero_full ^ 1, l + (zero_full ^ 1))
    return r == sum(t) and l == len(t)


A: Straight forward way
boolean isPandigital(int num,int length){
    for(int i=1;i<=length;i++){
        if(!(num+"").contains(i+""))
            return false;
    }
    return true;
}

OR if you are sure that the number is of the right length already
static boolean isPandigital(int num){
    for(int i=1;i<=(num+"").length();i++){
        if(!(num+"").contains(i+""))
            return false;
    }
    return true;
}


A: I refactored Andras' answer for Swift:
extension Int {

    func isPandigital() -> Bool {

        let requiredBitmask = 0b1111111111;
        let minimumPandigitalNumber = 1023456789;

        if self >= minimumPandigitalNumber {

            var resultBitmask = 0b0;
            var digits = self;

            while digits != 0 {

                let lastDigit = digits % 10;
                let binaryCodedDigit = 1 << lastDigit;

                resultBitmask |= binaryCodedDigit;

                // remove last digit
                digits /= 10;
            }

            return resultBitmask == requiredBitmask;
        }

        return false;
    }
}


1023456789.isPandigital(); // true


A: great answers, my 2 cents
bool IsPandigital(long long number, int n){

int arr[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, amax = 0, amin;
while (number > 0){

    int rem = number % 10;

    arr[rem]--;

    if (arr[rem] < 0)
        return false;

    number = number / 10;
}

for (int i = 0; i < n; i++){

    if (i == 0)
        amin = arr[i];

    if (arr[i] > amax)
        amax = arr[i];

    if (arr[i] < amin)
        amin = arr[i];
}

if (amax == 0 && amin == 0)
    return true;
else
    return false;

}
