Problem 28: Number spiral diagonals

*Difficulty: Medium

Problem:

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  13

It 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?

How to solve:

I sat down and started analyzing the problem, after many tries, I figured out this solution:

We got 4 diagonals in total, 1 goes from 1 to 9, named sum1, 1 goes from 1 to 3, named sum2, 1 goes from 1 to 5, named sum 3, and one goes from 1 to 7, named sum 4 (4 different directions).

  • The first four numbers on sum1 are 1,9,25,49

9-1 = 8 (base)

25-9 = 8*1 + base

49-25 = 8*2 + base

let i goes from 1 to n/2-1 (exclusive), n>=7, n is an odd number, cur1 is initialized with 9, base1 = 9-1 = 8, then sum1 will be calculated as

 

 

Screen Shot 2016-07-05 at 12.39.54 PM

  • The first four numbers on sum2 are 1,3,13,31

3-1 = 2 (base)

13-3 = 8*1 + base

31-3 = 8*2 + base

let i goes from 1 to n/2-1 (exclusive), n>= 7, n is an odd number, cur2 is initialized with 3, base2 = 3-1=2, then sum2 will be calculated as

Screen Shot 2016-07-05 at 12.41.25 PM

  • The first four numbers on sum3 are 1,5,17,37

5 – 1 = 4 (base)

17-5 = 8*1 + base

37-17 = 8*2 + base

let i goes from 1 to n/2-1 (exclusive), n >= 7, n is an odd number, cur3 is initialized with 5, base3 = 5-1=4, then sum3 will be calculated as

Screen Shot 2016-07-05 at 12.44.42 PM

  • Last but not least, the first four numbers on sum4 are 1,7,21,43

7-1 = 6 (base)

21-7 = 8*1+base

43-21 = 8*2+base

let i goes from 1 to n/2-1 (exclusive), n>=7, n is an odd number, cur4 is initialized with 7, base4 = 7-1=6, then sum4 will be calculated as

Screen Shot 2016-07-05 at 12.47.33 PM

This is how you combine the 4 for-loop above:

Screen Shot 2016-07-05 at 12.55.24 PM

There you go, if you reach here, means you’ve calculated the sum of all number (except 1) on all four diagonals. The last work you need to do is just adding sum1,sum2,sum3,sum4 and plus 1.

Screen Shot 2016-07-05 at 12.49.27 PM

This way, you can calculate sum of all numbers on the diagonals in a spiral with any size >= 7. How about 1,3,5, sadly, you have to do it by yourself.

Screen Shot 2016-07-05 at 12.53.03 PM

Solution took 0 ms with size = 1001

 

 

Advertisements