How many squares are there in an N x M grid
So I came across this question last night and solved it this morning. Here is my approach:
Problem
If you have an n x m grid, how many squares can you color inside the grid. For example, a 2x3 grid has 8 squares in it as shown below:
Solution
The trick to solving this question (or this sort of question for that matter) is patience. You need to break the problem into smaller pieces or easier parts and then try to generalize your answer.
Since a 2x3 grid has the same number of squares as a 3x2 grid, I decided to make my life easier and reword the question to “number of squares in an nxm grid where m >= n”.
Since n is always smaller than m, we can also conclude that our grid will have at most squares of size n x n. Therefore we need to sum the number squares of size 1x1 + 2x2 + … + n x n.
Starting with the simplest case here, a 1x1 grid has 1 square. It is also easy to see that a 1 x m grid has m (or 1*m) 1x1 squares.
2x2
a 2x2 grid has 4 1x1 squares and a single 2x2 square = 5.
a 2x3 grid has 6 1x1 (2 * 3) squares and 2 2x2 (2 * 1) squares = 8. (we solved this above.)
If you continue this you can easily see that a 2 x m grid has 2*m + 1*(m — 1) squares in it. Let’s move on to the next step!!
3x3
a 3x3 grid has 9 1x1 (3 * 3) squares 4 2x2 (2 * 2) squares and a single 3x3 square = 14.
a 3x4 grid has 12 1x1 (3 * 4) squares 6 2x2 (2 * 3) squares and 2 3x3 squares = 20.
Again, if you continue this you can find that a 3 x m grid has 3*m + 2*(m-1) + 1*(m-2) squares. At this point if you compare our result for 3xm and 2xm you can see a pattern. So let’s generalize our solution.
Generalize for n x m
an n x m grid has n*m + (n-1)*(m-1) + (n-2)*(m-2) + … + (n-(n-1))*(m-(n-1)) squares. Since I have just started to learn the Go Language, it was a perfect practice for me to write a program to solve this question, I’ve included the source below.
/**
* I'm using my own versions of max and min because
* Math package only has max() float64 and min() float64
*/
func max (a,b int) int {
if a > b {
return a
} else {
return b
}
return 0
}
func min (a,b int) int {
if a < b {
return a
} else {
return b
}
return 0
}
func count(n, m int) int {
s, b := min(n, m), max(n, m)
r := 0
for i := 1; i <= s; i++ {
r += (s - i + 1) * (b - i + 1)
}
return r
}
func main() {
fmt.Print(count(2,3));
}Fun
While playing with the count() function I saw that 4 x m has a very interesting pattern!
4x3 = 20
4x4 = 30
4x5 = 40
4x6 = 50
4x7 = 60
4x8 = 70
4x9 = 80// Guess what is the next value!
To challenge yourself try and solve the same question except with rectangles! i.e. “How many rectangles are there in an n x m grid?”.
Good luck.
Originally published at wordrump.com.
