# SNAKE - Editorial

Author: Aayush Agarwal
Tester: Aayush Agarwal
Editorialist: Aakash Jain

SIMPLE-EASY

Elementary Maths

### PROBLEM:

Form an NxN matrix following the given snaking pattern starting at the bottom left (example for 4x4):

``````7 13 14 16
6  8 12 15
2  5  9 11
1  3  4 10
``````

Report the value at (X, Y).

### QUICK EXPLANATION:

Divide the matrix along the principal diagonal. First fill the bottom half along the diagonals, changing the limits appropriately for each diagonal. Use a flag variable to indicate the direction in which the diagonal is to be filled, and flip it after each diagonal. Repeat the process for the upper half of the matrix.

### EXPLANATION:

We can divide the problem into two loops, each filling one half of the NxN matrix. We divide a 4x4 matrix as follows:

``````x o o o
x x o o
x x x o
x x x x
``````

The halves will be filled diagonally. We will be needing the following variables for our task:

• A counter that tells us the value to be stored at each place in the matrix.
• A flag variable that we flip after filling each diagonal. Its value tells us the direction in which to fill the current diagonal.
• The top and bottom row numbers for the current diagonal.
• The leftmost and rightmost column numbers for the current diagonal.

First we will fill the lower half, starting at the bottom right. For this, we initialize our variables as follows:

``````value = 1
direction = 1
rowTop = rowBottom = N-1
colLeft = colRight = 0
``````

For each successive diagonal, you will find that we have to decrement `rowTop` and increment `colRight`. We also have to flip `direction` (this can be done by XORing it with 1). To fill each diagonal, we check the value of `direction`. If it is 1, we fill the diagonal from bottom to top (equivalently, right to left). If it is 0, we fill from top to bottom (equivalently, left to right).
Pseudo-code:

``````while rowTop >= 0
if direction == 0
i = rowTop
j = colLeft
while i <= rowBottom
matrix[i][j] = value++
i++
j++
else
i = rowBottom
j = colRight
while i >= rowTop
matrix[i][j] = value++
i--
j--
rowTop--
colRight++
direction ^= 1
``````

We have now filled the lower half of the matrix. Next, we will be starting with the lowest diagonal of the top half and moving to the top right. This is similar to what we did for the lower half, with some changes. Pseudo-code:

``````rowTop = 0
rowBottom = N-2
colLeft = 1
colRight = N-1
while rowBottom >= 0
if direction == 0
i = rowTop
j = colLeft
while i <= rowBottom
matrix[i][j] = value++
i++
j++
else
i = rowBottom
j = colRight
while i >= rowTop
matrix[i][j] = value++
i--
j--
rowBottom--
colLeft++
direction ^= 1
``````

We have now filled the matrix and simply have to return `matrix[X][Y]`. Optionally, we could return our value as soon as the value at `matrix[X][Y]` is filled, instead of filling the entire matrix first.

### AUTHORâ€™S SOLUTION:

Authorâ€™s solution can be found here.