Given a m x n rectangle, how many squares are there in it?

Examples :

Input: m = 2, n = 2

Output: 5

There are 4 squares of size 1x1 + 1 square of size 2x2.

Input: m = 4, n = 3

Output: 20

There are 12 squares of size 1x1 +

6 squares of size 2x2 +

2 squares of size 3x3.

**Let us first solve this problem for m = n, i.e., for a square:**

For m = n = 1, output: 1

For m = n = 2, output: 4 + 1 [ 4 of size 1×1 + 1 of size 2×2 ]

For m = n = 3, output: 9 + 4 + 1 [ 9 of size 1×1 + 4 of size 2×2 + 1 of size 3×3 ]

For m = n = 4, output 16 + 9 + 4 + 1 [ 16 of size 1×1 + 9 of size 2×2 + 4 of size 3×3 + 1 of size 4×4 ]

In general, it seems to be n^2 + (n-1)^2 + … 1 = n(n+1)(2n+1)/6

**Let us solve this problem when m may not be equal to n:**

Let us assume that m <= n

From above explanation, we know that number of squares in a m x m matrix is m(m+1)(2m+1)/6

What happens when we add a column, i.e., what is the number of squares in m x (m+1) matrix?

When we add a column, number of squares increased is m + (m-1) + … + 3 + 2 + 1

[ m squares of size 1×1 + (m-1) squares of size 2×2 + … + 1 square of size m x m ]

Which is equal to m(m+1)/2

So when we add (n-m) columns, total number of squares increased is (n-m)*m(m+1)/2.

So total number of squares is m(m+1)(2m+1)/6 + (n-m)*m(m+1)/2.

Using same logic we can prove when n <= m.

So, in general,

Total number of squares = m x (m+1) x (2m+1)/6 + (n-m) x m x (m+1)/2 when n is larger dimension

Using above logic for rectangle, we can also prove that number of squares in a square is n(n+1)(2n+1)/6

Below is the implementation of above formula.

`// Java program to count squares`

`// in a rectangle of size m x n`

`class`

`GFG`

`{`

` `

`// Returns count of all squares`

` `

`// in a rectangle of size m x n`

` `

`static`

`int`

`countSquares(`

`int`

`m, `

`int`

`n)`

` `

`{`

` `

`// If n is smaller, swap m and n`

` `

`if`

`(n < m)`

` `

`{`

` `

`// swap(m, n)`

` `

`int`

`temp = m;`

` `

`m = n;`

` `

`n = temp;`

` `

`}`

` `

` `

` `

`// Now n is greater dimension,`

` `

`// apply formula`

` `

`return`

`m * (m + `

`1`

`) * (`

`2`

`* m + `

`1`

`) /`

` `

`6`

`+ (n - m) * m * (m + `

`1`

`) / `

`2`

`;`

` `

`}`

` `

` `

`// Driver Code`

` `

`public`

`static`

`void`

`main(String[] args)`

` `

`{`

` `

`int`

`m = `

`4`

`, n = `

`3`

`;`

` `

`System.out.println(`

`"Count of squares is "`

`+`

` `

`countSquares(m, n));`

` `

`}`

`}`

**Output :**

Count of Squares is 20

**Alternate Solution :**

- Let us take m = 2, n = 3;
- The number of squares of side 1 will be 6 as there will be two cases one as squares of 1-unit sides along with the horizontal(2) and the second case as squares of 1-unit sides along the vertical(3). that give us 2*3 = 6 squares.
- When the side is 2 units, one case will be as squares of the side of 2 units along only one place horizontally and the second case as two places vertically. So, the number of squares=2
- So we can deduce that, Number of squares of size 1
*1 will be m*n. The number of squares of size 2*2 will be (n-1)(m-1). So like this, the number of squares of size n will be 1*(m-n+1).

The final formula for the total number of squares will be * n(n+1)(3m-n+1)/6** .

`// Java program to count squares`

`// in a rectangle of size m x n`

`import`

`java.util.*;`

`class`

`GFG`

`{`

` `

`// Returns count of all squares`

` `

`// in a rectangle of size m x n`

` `

`static`

`int`

`countSquares(`

`int`

`m, `

`int`

`n)`

` `

`{`

` `

`// If n is smaller, swap m and n`

` `

`if`

`(n < m)`

` `

`{`

` `

`int`

`temp = m;`

` `

`m = n;`

` `

`n = temp;`

` `

`}`

` `

`// Now n is greater dimension,`

` `

`// apply formula`

` `

`return`

`n * (n + `

`1`

`) * (`

`3`

`* m - n + `

`1`

`) / `

`6`

`;`

` `

`}`

` `

`// Driver Code`

` `

`public`

`static`

`void`

`main(String[] args)`

` `

`{`

` `

`int`

`m = `

`4`

`;`

` `

`int`

`n = `

`3`

`;`

` `

`System.out.print(`

`"Count of squares is "`

`+`

` `

`countSquares(m, n));`

` `

`}`

`}`

**Output :**

Count of Squares is 20