Как найти количество квадратов размещенных на прямоугольнике

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. 

Output : 

Count of Squares is 20

Time complexity: O(1)

Auxiliary Space: O(1)

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 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 .

Output : 

Count of Squares is 20

Time complexity: O(1)

Auxiliary Space: O(1)

Thanks to Pranav for providing this alternate solution.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Approach#3: Using loop

This approach counts the number of squares in a given rectangle of size m x n by iterating over all possible square sizes from 1 to the minimum of m and n, and adding up the number of squares of each size that can fit in the rectangle. 

Algorithm

1. Initialize a counter variable to 0.
2. Iterate over all possible square sizes, i.e. from 1 to min(m, n).
3. For each square size, calculate the number of squares that can be formed.
4. Add this count to the counter variable.
5. Return the final count.

Time Complexity: O(m * n * min(m, n))
Space Complexity: O(1)

Last Updated :
28 Apr, 2023

Like Article

Save Article

Дан прямоугольник из N×M квадратов. Назовём квадраты на границе прямоугольника крайними. Расстоянием от какого‑либо квадрата до края назовём количество перемещений, которое нужно сделать из данного квадрата в соседний по стороне квадрат, чтобы добраться от данного квадрата до крайнего квадрата. Квадраты с максимальным расстоянием до края, будем называть центральными. При этом квадрат может быть одновременно и крайним, и центральным.

На рисунке изображён прямоугольник для N=7 и M=8, в каждом квадрате которого записано расстояние от этого квадрата до края. У этого прямоугольника два центральных квадрата.

По данным N и M определите количество центральных квадратов в прямоугольнике.

Формат входных данных

Программа получает на вход два целых положительных числа, записанных в разных строках, не превосходящих 109 — размеры прямоугольника.

Формат выходных данных

Программа должна вывести одно число — количество центральных клеток в данном прямоугольнике.

(Visited 282 times, 1 visits today)

Dwasedma ответил на вопрос 25.10.2022

Имеется миллиметровка со сторонами n на m, нужно посчитать количество всех квадратов границы которых проходят по границам клеток. (Точнее, вывести формулу).

Формулу подсчёта квадратов на квадратной шахматной доске знаю:
$$sumlimits_{k=1}^nk^2=frac{n∙(n+1)∙(2∙n+1)}6$$

Из [math.hashcode.ru/questions/40893/

Для начала я писал такие примеры,
для прямоугольника:
2х1 $$1 times 1+1=2 $$ $$квадрата $$
3х2 $$(1 times 1+1)+(2 times 2+2)=8 $$$$квадратов $$
4х3 $$(1 times 1+1)+(2 times 2+2)+(3 times 3+3)=20$$$$квадратов $$
3х1 $$1 times 1+1+1=3 $$$$квадрата $$
4х2 $$(1 times 1+1+1)+(2 times 2+2+2)=11$$$$квадратов $$
5×3 $$(1 times 1+1+1)+(2 times 2+2+2)+(3 times 3+3+3)=26$$$$квадратов $$