Project Euler : Concealed Square

Problem 206

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.

Solution (in Ruby)

Before we look at the optimal solution, lets look at what brute force has to offer us. There are nine slots in the number which leaves us to iterate on 1000000000 times (1 trillion times). This is simply not doable, it will take years to run through this loop. So brute force is out of the equation. We need to find a digit or two to reduce the loop count.

So its wiser to look at some of the property of square numbers. Square number ending with zero, has to have the previous digit also 0, which leaves us with only 8 slots now. One more property is that the square root for this particular number has to start with 1. The reason is in finding the square root, we need pair numbers from the back and need to find the square root of the first hanging digit/pair. In this case its 1. Square root 1 is 1 and its enough to inspect only one digit. This leaves us 1 more slot less in our problem. And one final property is the ending digit. Here its 9. Only numbers that end with 3 and 7 produces 9. This leaves our permutation reduce by one more digit (since its enough for us to step 10 times every time in the loop). We need to find the lower bound of the number which is 10203040506070809. The square root of this number is 101010101. We shall end with either 3 or 7. And start with the maximum digit in that sequence which is 199999999. Thats it!! Now we've shortened the problem to be solved within seconds!!


Hover here to see the solution

Cheers!!
Bragaadeesh