Part A:
Assuming that array indices start with 0, consider that for array A, A[n][n] - A[n][0] == A[n][n] - A[0][n], since we iterate by 1 from A[n][0] to A[n][n], then to A[0][n]. [n][n].
We can see from the illustration that A[0][n] == (n + 1)^2, which is because it is the final number of a square. This satisfies the base case A[0][0], since (0 + 1)^2 == 1.
We can further determine that A[n][0] = n^2 + 1, since A[n][0] always follows A[0][n]; in this case, A[n][0] is the square of the number of rows rows - 1, which is n. This also satisfies the base case, since 0 ^2 + 1 == 1.
Given this data, we can proceed with the following pseudo-code:
if i < j then
k := (max(i, jj) + 1) ^ 2;
k := k - i;
else if i > j then
k := (max(i, j)^2 + 1;
k := k + j;
else
k := (i + 1)^2 - i;
If there are less columns than rows, then we decrement from the bottom left, starting from A{0][n]. If there are more columns than rows, then we increment from the top right, starting from A[n][0]. If the number of rows and columns are equal, then we square the number of rows and substract from it the number of rows to obtain the number in the bottom left corner.
In C we can implement this algorithm as follows:
#include "math.h"
{int getIndexFromShellArray(int i, int j, int[] A)
{
int k;
if (i < j)
{
k = pow(max(i, j) + 1, 2);
k -= i;
}
else if (i < j)
{
k = pow(max(i, j)) + 1;
k += j;
}
else
k = pow(i + 1, 2) - i;
return A[k];
}
int max(int x, int y)
{
return (x >= y) ? x : y;
}