Finding the number at a specific index of spirally filled matrix

user_13333833 0
Viewed 54

The problem is as follows:

We have 3 integer values as input: n, i, j Suppose we have n × n matrix, that is filled with numbers from 1 to n² in clockwise spiral way. Find the number at the index (i, j).

I know how to construct such matrix, I can solve it by filling the matrix and looking at the index (i, j), and I consider such solution a bit too "brute force". I believe there should be some mathematical relationship between the number n, the indices i, j and the number sitting at that cell. I've tried some approaches but couldn't find a way to do it. Any suggestions to help me in my attempt?

Edit: an example 5x5 matrix:

1  2  3  4  5 
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
matrix algorithm
1 Answers

You can do it with some basic arithmetic (assuming 0-based indexing, i stands for the row and j for the column):

  1. Find the ring in which the number is in. It is r = min(i, j, n - i - 1, n - j - 1). This is counting the rings from outer to inner. If we count from inside to outside (which will come in handy later), then we get q = (n - 1) / 2 - r for odd n or q = (n - 2) / 2 - r for even n. Or generalized: q = (n - 2 + n % 2) / 2 - r which is the same as q = (n - 1) / 2 - r for integer division (as mentioned by @Stef).

  2. It is not that hard to see that the number of elements covered by a ring (including the numbers inside of it) from most inner going outwards is 1^2, 3^2, 5^2, ... if n is odd and 2^2, 4^2, 6^2, ... if n is even. So the side length of the square covered by ring q is (in generalized form) m = q * 2 + 2 - n % 2. This means the element in the upper left corner of the ring is b = n^2 - m^2 + 1.

  3. Get the number:

    1. If r == i: b + j - r (element is on top side).

    2. If r == n - j - 1: b + m - 1 + i - r (element is on the right side)

    3. If r == n - i - 1: b + 2 * m - 2 + n - j - 1 - r (element is on the bottom)

    4. Otherwise (r == j): b + 3 * m - 3 + n - i - 1 - r (element is on the left side)

This is O(1). The formulas can be simplified, but then the explanation would be harder to understand.

Example: n = 5, i = 3, j = 2

  1. r = min(2, 3, 1, 2) = 1, q = (3 + 1) / 2 - 1 = 1
  2. m = 2 + 2 - 1 = 3, b = 25 - 9 + 1 = 17
  3. Third condition applies: 17 + 6 - 2 + 5 - 2 - 1 - 1 = 22
user_47851100
Related