Ajay - 1 year ago 99

PHP Question

I have a n*n spiral matrix.

if N = 4

then matrix :

`7 8 9 10`

6 1 2 11

5 4 3 12

16 15 14 13

if N = 3

`7 8 9`

6 1 2

5 4 3

I want to get the diagonal values of this spiral matrix.

In the

`n=4`

I can do this by storing this matrix in array and traversing for each diagonal value.

Is there any better way to get these values.

Answer Source

To get the numbers on the main diagonal, we can notice that the values are

```
1 = 1
1 + 2 = 3
1 + 2 + 4 = 7
1 + 2 + 4 + 6 = 13
```

So the general formula is 1 + (sum i = 0 to k of 2*i) for k = 0, 1, 2, ... Simplifying this, we get k^2 + k + 1 for k = 0, 1, 2, ...

In PHP, we can generate these via something like this:

```
function mainDiagonal($n) {
$values = array();
for ($k = 0; $k < $n; $k++) {
$values[] = $k*$k + $k + 1;
}
return $values;
}
```

To get the numbers on the antidiagonal for even N we see:

```
2 = 2
2 + 2 = 4
2 + 2 + 6 = 10
2 + 2 + 6 + 6 = 16
```

If we continue this pattern for larger matrices we see the general formula is

sum i = 0 to k of floor(i/2)*4 + 2 for k = 0, 1, 2, ...

Similarly for odd N we find the formula is

1 + (sum i = 0 to k of ceil(i/2)*4) for k = 0, 1, 2, ...

In PHP, we can generate these via something like this:

```
function antiDiagonal($n) {
$values = array();
if ($n % 2 == 0) {
for ($k = 0; $k < $n; $k++) {
$accum = 0;
for ($j = 0; $j <= $k; $j++) {
$accum += floor($j/2)*4 + 2;
}
$values[] = $accum;
}
} else {
for ($k = 0; $k < $n; $k++) {
$accum = 1;
for ($j = 0; $j <= $k; $j++) {
$accum += ceil($j/2)*4;
}
$values[] = $accum;
}
}
return $values;
}
```

Notice that the maximum value of k is one less than the dimension of the matrix.

Combining these functions, we obtain:

```
array_unique(array_merge(mainDiagonal($n), antiDiagonal($n)))
```