Tao of Coding

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

First thought was brute force by replacing blanks with numbers, and checking for a square root. This comes to a mere 10^9 possibilities, with a lot of parsing longs from string. After a bit of analysis though, you realize the last digit of the number we are looking for has to be 0. (0 being the only a*a to result in a 0 digit at the end). This also means the first blank is a 0, giving a mere 10^8 possibilities. Next is to realize that 9 can only be formed by a 3, or a 7 in the number. (Try not to forget the 7, as I did the first time through). So, we now know the target square ends in either 70 or 30.

We can move away a lot of parsing longs from strings, and sqrt’s, by just iterating over the possible answers, rather then the possible answers^2. This basically means iterating from 10^9+30 to something less then 10^10 (sqrt of 1929394959697989900; though I’m far too boring to plug that into a calculator). As already stated, we’re looking for something ending in 30 or 70, so we could start with 10^9+30 and increment by 100, then switch to +70, or alternatively alter increments of 40 and 60.

Probably the most complex thing is checking whether or not a square is of the desired format. For that I get the string representation of the square, and then in a for loop check that every other character is incrementing; with a special check for the 0 case. I envision there are better ways, but this was good enough for this problem.

Code:

static void Main(string[] args)
{
    long start = 1000000000;
    //add 100 to long on the off chance that there's a terrible loss
    //  of precision in the constant double
    long end = (long)(Math.Sqrt(1929394959697989900))+100;
    Test(start + 30, end, 100);
    Test(start + 70, end, 100);
}
static void Test(long start, long end, long incr)
{
    for (long current = start; current < end; current += incr)
    {
        string squareString = (current * current).ToString();
        bool isValid = true;
        for (int i = 1; i <= 9 && isValid; i++)
            if (squareString[2 * (i - 1)] != '0' + i)
                isValid = false;
        if (squareString[2 * (10 - 1)] != '0')
            isValid = false;
        if (isValid)
            Console.WriteLine("Solution: " + current);
    }
}

Tags: project euler

This entry was posted on Saturday, May 9th, 2009 at 12:03 by Matt and is filed under Contest Stuff. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.