Matrix Checkerboard

We wish to find, for an arbitrary N, an N x N matrix with the following property: each entry in the matrix is the smallest non-negative number which does not appear either above the entry or to its left.

For example, for N=6, we might have the matrix:

0	1	2	3	4	5
1	0	3	2	5	4
2	3	0	1	6	7
3	2	1	0	7	6
4	5	6	7	0	1
5	4	7	6	1	0

1. Write a function that computes the entry in a particular row and column. That is, complete the following:
   
   int entry_at(int row, int column) {
   
       // ...
   
   }
   
   
2. Can you write the entry_at function to run in constant space and constant time?

Soln: Assume we count rows and columns starting with 0: 0, 1, 2, and so on. Let a_mn denote the number that appears in the (m, n)-cell. Then

amn = m ^ n.

It follows that this particular Latin square serves as the "addition" table for the XOR operation over the set of nonnegative integers. In particular, using the binary representation,

a100, 1000 = 100 ^ 1000 = (1100100)2 ^ (1111101000)2 = (1110001100)2 = 908.

[Of course, if initially rows and columns were counted starting with 1, then we should consider instead 99 ^ 999 which is 900!]

Tweet