Project Euler

Problem 38: Pandigital Multiples

Take the number 192 and multiply it by each of 1, 2, and 3:
192 x 1 = 192
192 x 2 = 384
192 x 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3). The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ..., n) where n > 1?

The Catch

How to find the optimal range of a candidate number c, which is to be multiplied with (1, 2, ... n) where n > 1 to form the concatenated-product-pandigital number.
How to check if a number is pandigital.

The Light

The desired pandigital number p has to have 9 digits from 1-9, exactly once each. A candidate number c has to be multiplied with 1 to n, with n > 1. The products are then concatenated to form p. Define the notation (a)(b) to be "a concatenates b", or ab. To find the range of c, observe:

• c has to have less than 5 digits because the smallest 5-digit number is 10,000 and the smallest possible value for n is 2 (n > 1). This gives (10,000 * 1)(10,000 * 2) = 1,000,020,000, which has 10 digits and thus does not satisfy the 9-digit condition. Thus c < 10,000.
• We were given to start with 9, so c has to start with 9. Thus 9 <= c < 9,999.
• If c has 2 digits, its lowest value is 90. Assume n = 2 (lowest possible value), (90 * 1)(90 * 2) = 90,180, which does not satisfy the 9-digit condition. n = 3 gives 90,180,270 and n = 4 gives 90,180,270,360, both of which do not satisfy the 9-digit condition. Thus 90 <= c < 9,999.
• If c has 3 digits, its lowest value is 900. Assume n = 2 (lowest possible value), (900 * 1)(900 * 2) = 9,001,800, which does not satisfy the 9-digit condition. n = 3 gives 90,018,002,700 and n = 4 gives 900,180,027,003,600, both of which do not satisfy the 9-digit condition. Thus 900 <= c < 9,999.
• If c has 4 digits, its lowest value is 9,000. Assume n = 2 (lowest possible value), (9,000 * 1)(9,000 * 2) = 900,018,000, which satisfies the 9-digit condition. n = 3 gives 90,001,800,027,000, violating the 9-digit condition, thus any n > 2 will not work.
• Range for candidate c is 9,000 <= c < 9,999 and n can only be 2.

Since we're looking for the largest instance, start with the greatest possible c candidate and decrement.

Follow the discussion in Problem 41 to check if a number is pandigital.

The Code

import java.util.Arrays;

public class Problem38
{
  public static char[][] p = {"1".toCharArray(), "12".toCharArray(), 
                              "123".toCharArray(), "1234".toCharArray(),
                              "12345".toCharArray(), "123456".toCharArray(), 
                              "1234567".toCharArray(), "12345678".toCharArray(), 
                              "123456789".toCharArray()};

  public static void main(String[] args)
  {
    for(int i = 9999; i >= 9000; i--)
    {
      String s = Integer.toString(i);
      s = s.concat(Integer.toString(i*2));	  
      if(isPan(s))
      {
        System.out.println(s);
    	break;
      }
    }
  }

  public static boolean isPan(String s)
  {
    char[] c = s.toCharArray();
    Arrays.sort(c);
    return (Arrays.equals(c, p[c.length - 1]));	
  }
}