Spiral square diagonals
Published on Friday, July 29, 2011Problem 28 is the last problem I'll be tackling today and the first trick question I've encountered on Project Euler. Take note of both the diction and the example given:
Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?
They keep calling that shape a spiral, but it sure looks like a square to me. And indeed, recognizing that it's a square is the key to solving this problem quickly and efficiently. Notice that the top left corner of each of the concentric squares in our “spiral” is the square of the length of that square's sides. The other corners can be easily derived from the top left, as we already know the length of the square's sides.
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem028 { class Program { static void Main(string[] args) { int runningTotal = 1; // Center of the spiral for (int i = 3; i < 1002; i += 2) { int corner1 = i * i; int corner2 = corner1 - (i - 1); int corner3 = corner2 - (i - 1); int corner4 = corner3 - (i - 1); runningTotal += corner1 + corner2 + corner3 + corner4; } Console.WriteLine(runningTotal); } } }