Sunday, September 12, 2010
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
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).
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.
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.