Euler 038- Find the largest 1..9 pandigital
A simple problem for today. A 1..9 Pandigital is defined as a nine digit number that contains digits 1 through 9. Find the largest pandigital that can be formed by concatenated multiplications. Specifically, given a number (192), multiply by, say, 1, 2, and 3 to get 192, 384, 576; the concatenated multiplication would be 192384576; which happens to be a pandigital. Multiplication factors have to be increasing, (1,2; 1,2,3; etc); and can’t be only 1.
So, my simple approach involves trying number of factors (n) of 2 through 8, and iterating through all possible factors that should be roughly less then a 9 digit number. Roughly/maybe/sort of. Overall the code isn’t that complex.
At least one optimization exists in realizing that the first digit of the factor has to be a 9, limiting the number of numbers to try; though in this case iterating over all possibilities is fast enough that that doesn’t really factor in.
public static void Main() { //the only pangdigital with n=9 is 1 //n>1 is required List<string> panDigitals = new List<string>(); for (int n = 2; n < 9; n++) panDigitals.AddRange(FindPandigitals(n)); panDigitals.Sort(); foreach (string pan in panDigitals) Console.WriteLine(pan); } public static List<string> FindPandigitals(int n) { List<string> results = new List<string>(); int digitCount=(9/n)+1; int maxI = (int)Math.Pow(10, digitCount); for(int i=1; i<maxI; i++) { string s=""; for (int a = 1; a <= n; a++) s += i * a; if (IsPandigital(s)) results.Add(s); } return results; } public static bool IsPandigital(string s) { if (s.Length != 9) return false; for (char a = '1'; a <= '9'; a++) if (!s.Contains(a)) return false; return true; }
Side note: I suspect next I’m going to try an ACM problem… or maybe something from Google CodeJam… who knows?
Tags: project euler
