Find the total number of squares and rectangles in an NxN chessboard.

12th, September, 2010

Asked here http://geeksforgeeks.org/forum/topic/interview-question-for-software-engineerdeveloper-about-puzzle-4#post-7819

Solution:

For example, consider 8 X 8 chess board.

Note that we need 9 integers to represent one side (say x-axis) of the chess board. Similarly we need 9 integers on other side (say y-axis).

Rectangles:

Every square is a rectangle. A rectangle requires two co-ordinates (horizontal line) on x-axis and two co-ordinates (vertical line) on y-axis. The horizontal line needs two integers out of these 9 integers on x-axis. Similarly the vertical line needs two integers out of 9 on the y-axis. Hence we can draw the horizontal line in 9C2 different ways, and same with vertical line. Overall we can have (9C2)*(9C2) = (36)*(36) = 1296 rectangles on the chess board.

Squares:

There is simple approach to figure out squares.

Draw one simple rectangle with consecutive integers. We can have only one rectangle.

Take any two consecutive integers on x and y axis, there will be 1 (outer) + 4 (individual) squares.

Take any three consecutive integers on x and y axis, there will be 1 (outer) + 4 (dual) + 9 (individual) squares.

Take any four consecutive integers on x and y axis, there will be 1 (outer) + 4 (triple) + 9 (dual) + 16 (individual) squares.

Note that there is a pattern. So, for 8 consecutive integers on x and y axis there will be

1 + 4 + 9 + ... + 49 + 64

= n(n+1)(2n+1)/6 (where n = 8)

= 204 Squares.

I think there is simple approach using binomial co-efficients. Try it.

You can generalize the approach for N X N chess board.