Count number of squares in a rectangle

Software Development
#1

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 :

  1. Let us take m = 2, n = 3;
  2. 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.
  3. 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
  4. So we can deduce that, Number of squares of size 11 will be mn. The number of squares of size 22 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