Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

euler
c++
pyhton

How to solve the 'number spiral diagonals' problem

Educative Answers Team
svg viewer

A spiral diagonal is formed when you take a number, 1, and increase that number as you move to the right and below. This forms a spiral.

The following slides show how a number spiral is formed for a 4x4 matrix.

1 of 9

The sum of the diagonals in a 3x3 number spiral is 2525.

In the number spirals diagonal problem, the sum of diagonals for nxn needs to be found.

If one looks closely, one can find a pattern. Consider the following matrix.

The values in each diagonal correspond to:

an=(9,25,49,81...)a_{n} = (9, 25, 49, 81 ...) bn=(7,21,43,73...)b_{n} = (7, 21, 43, 73 ...) cn=(5,17,37,65...)c_{n} = (5, 17, 37, 65 ...) dn=(3,13,31,57...)d_{n} = (3, 13, 31, 57 ...)

These correspond to the following sequence:

an=4n2+4n+1a_{n} = 4n^2+4n+1 bn=4n2+2n+1b_{n} = 4n^2+2n+1
cn=4n2+1c_{n} = 4n^2+1
dn=4n22n+1d_{n} = 4n^2-2n+1

The sum of all the terms includes the one in the center; therefore, it becomes:

Sum(n) = 1+k=1n(ai+bi+ci+di)1+ \sum_{k=1}^n (a_i + b_i + c_i + d_i)
Sum(n) = 1+k=1n(16i2+4i+4)1+\sum_{k=1}^n (16i^2 + 4i +4)
Sum(n) = 1+k=1n16i2+k=1n4i+k=1n41+\sum_{k=1}^n 16i^2 + \sum_{k=1}^n 4i + \sum_{k=1}^n4

Using summation rules we can reduce it to:

Sum(n) = 3+2n(8n2+15n+13)3\frac{3+2n(8n^2 + 15n +13)}{3}

This simple formula can then be used to calculate the sum of the diagonal for the matrix of any dimension.

Remember: Here, n equals 1/2 the number of elements in a diagonal, excluding the center term.

n = dim12\frac{dim-1}{2}

Where dim is the dimension of the matrix.

Code

The following code shows how to find the sum of the diagonal in a number spiral for an nxn matrix.

#include <iostream>
using namespace std;
// declare function sum
int sum(int dim)
{
  int n = (dim - 1) /2;//find n 
  // use the formula defined above
  int x = (3 + 2 * n * ( 8 * n * n + 15 * n +13)) /3;

  return x;
}
int main() {
  // call the function and print the value
  int diagonal = sum(5);
  cout << diagonal << endl;
  return 0;
}

RELATED TAGS

euler
c++
pyhton
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring