Project Euler Problem #43!

July 27th, 2009
by Serinox

Problem #43 says:

The number, 1406357289, is a 0 to 9 pandigital number because
 it is made up of each of the digits 0 to 9 in some order, but it also
has a rather interesting sub-string divisibility property.

Let d_(1) be the 1^(st) digit, d_(2) be the 2^(nd) digit, and so on.
In this way, we note the following:

    * d_(2)d_(3)d_(4)=406 is divisible by 2
    * d_(3)d_(4)d_(5)=063 is divisible by 3
    * d_(4)d_(5)d_(6)=635 is divisible by 5
    * d_(5)d_(6)d_(7)=357 is divisible by 7
    * d_(6)d_(7)d_(8)=572 is divisible by 11
    * d_(7)d_(8)d_(9)=728 is divisible by 13
    * d_(8)d_(9)d_(10)=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

This Problem along with problem #41 were done as battery test for my new computer and use a brute force method to solve the problem with little or no optimization. Therefor they take a long time to run. I will probably return at some point and see if i cannot speed things up. Until then Solution in C#/mono.

using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace ProjectEuler
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            long Answer = 0;

            long Stepper = 1000000000;
            long Max = 9999999999;
            while (Stepper <= Max)
            {
                if (CheckNum(Stepper))
                {
                    Answer += Stepper;
                }
                if (Stepper % 5000000 == 0)
                {
                    Console.WriteLine(Stepper.ToString() +
                          " :: " + (((float)Stepper / (float)Max) * (float)100).ToString());

                }
                Stepper++;
            }

            Console.WriteLine(Answer);
            sw.Stop();
            Console.WriteLine(sw.Elapsed);
            Console.ReadLine();
        }
        static bool CheckNum(long num)
        {
            if (num.ToString().Length != 10)
            {
                return false;
            }
            if (IsPandigital(num) != 1)
            {
                return false;
            }
            string Num = num.ToString();
            int d1 = int.Parse(Num[0].ToString());
            int d2 = int.Parse(Num[1].ToString());
            int d3 = int.Parse(Num[2].ToString());
            int d4 = int.Parse(Num[3].ToString());
            int d5 = int.Parse(Num[4].ToString());
            int d6 = int.Parse(Num[5].ToString());
            int d7 = int.Parse(Num[6].ToString());
            int d8 = int.Parse(Num[7].ToString());
            int d9 = int.Parse(Num[8].ToString());
            int d10 = int.Parse(Num[9].ToString());

            if (((d2 * 100) + (d3 * 10) + d4) % 2 != 0)
            {
                return false;
            }
            if (((d3 * 100) + (d4 * 10) + d5) % 3 != 0)
            {
                return false;
            }
            if (((d4 * 100) + (d5 * 10) + d6) % 5 != 0)
            {
                return false;
            }
            if (((d5 * 100) + (d6 * 10) + d7) % 7 != 0)
            {
                return false;
            }
            if (((d6 * 100) + (d7 * 10) + d8) % 11 != 0)
            {
                return false;
            }
            if (((d7 * 100) + (d8 * 10) + d9) % 13 != 0)
            {
                return false;
            }
            if (((d8 * 100) + (d9 * 10) + d10) % 17 != 0)
            {
                return false;
            }
            return true;
        }
        static long IsPandigital(long i)
        {
            char[] I = i.ToString().ToCharArray();
            long[] counters = new long[9] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

            foreach (char c in I)
            {
                switch (c)
                {
                    case '1':
                        counters[0] += 1;
                        break;
                    case '2':
                        counters[1] += 1;
                        break;
                    case '3':
                        counters[2] += 1;
                        break;
                    case '4':
                        counters[3] += 1;
                        break;
                    case '5':
                        counters[4] += 1;
                        break;
                    case '6':
                        counters[5] += 1;
                        break;
                    case '7':
                        counters[6] += 1;
                        break;
                    case '8':
                        counters[7] += 1;
                        break;
                    case '9':
                        counters[8] += 1;
                        break;
                }
            }
            foreach (long Check in counters)
            {
                if (Check > 1)
                    return -1;
                if (Check == 0)
                    return 0;
            }

            return 1;
        }

    }
}

Posted in General | Comments (0)

No comments yet

Leave a Reply

You must be logged in to post a comment.