some algorithmic puzzles, tutorials, interview questions... and stuff...

Saturday, March 13, 2010

How to print a spiral of numbers 1 through N

Printing the numbers 1 through N in a spiral is asked on interviews sometimes and is a interesting puzzle to solve. The reverse process is also simple but I will not write it here.

The code here is quite simple, but it does not print the numbers thorough N in a spiral, instead it prints a matrix with size N in which numbers are arranged into a spiral. Assuming N is given (16 for example), identifying the matrix size is simply of matter of finding sqrt(n). The idea is to print the outer layer and move inward progressively until reaching the most inner layer.


   1:  #define N 4
   2:  int mat[N][N];
   3:   
   4:  void fillSpiral() {
   5:      int start = 0;
   6:      int end = N;
   7:      int k = 0;
   8:      while (end - start >= 1) {
   9:          for (int i = start; i < end; i++) {
  10:              mat[start][i] = k;
  11:              ++k;
  12:          }
  13:          for (int i = start + 1; i < end; i++) {
  14:              mat[i][end - 1] = k;
  15:              ++k;
  16:          }
  17:          for (int i = end - 2; i >= start; i--) {
  18:              mat[end - 1][i] = k;
  19:              ++k;
  20:          }
  21:          for (int i = end - 2; i >= start + 1; i--) {
  22:              mat[i][start] = k;
  23:              ++k;
  24:          }
  25:          ++start;
  26:          --end;
  27:      }
  28:  }
  29:   
  30:   
  31:  int main() {
  32:      memset(mat, 0, sizeof(mat));
  33:      fillSpiral();
  34:      for (int i = 0; i < N; i++) {
  35:          for (int j = 0; j < N; j++) {
  36:              cout << mat[i][j] << "\t";
  37:          }
  38:          cout << endl;
  39:      }
  40:      cout << endl << endl;
  41:      return 0;
  42:  }

And the result is something like this (notice the spiral):


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

No comments:

Post a Comment