We help IT Professionals succeed at work.

# count squares of different dimensions in a matrix

on
1,009 Views
I have a question. It isn't homework I just want to know the logic that must be applied in this program.

Suppose u r given a 4*3 rectangle like (take these values from user)

__________________________
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|

Now calculate the no. of squares in this rectangle like:
No. of squares of dimension 1 is 12
No. of squares of dimension 2 is 6
No. of squares of dimension 3 is 2
No. of squares of dimension 4 is 0
Total no. of squares are 20.

Thanks.
Comment
Watch Question

## View Solutions Only

CERTIFIED EXPERT
Top Expert 2009
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
CERTIFIED EXPERT
Top Expert 2012

Commented:
Well, the number of squres of the dimension 1*1 in a m*n-sized rectangle will always be m*n*...
CERTIFIED EXPERT
Top Expert 2009

Commented:
A few typo corrections :

0 = (4 - 3) * (3 - 0)

should have been :

0 = (4 - 3) * (3 - 3)

And I should have shown :

12 = 3 * 4

as :

12 = (4 - 0) * (3 - 0)
Data Warehouse / Database Architect
CERTIFIED EXPERT
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
Data Warehouse / Database Architect
CERTIFIED EXPERT

Commented:

I don't believe that it's that complicated.  :)

Counting all possible squares of size S in a rectangle size MxN is the expression that I posted.

( Length(Rectangle) - Side(Square) + 1 ) * ( Width(Rectangle) - Side(Square) + 1 )

that is,

(M - S + 1) * ( N - S + 1)

Kent

Commented:
If your expression is correct (and mine is too. :) ), then my expression is equivalent to the sum of (M-S+1)(N-S+1) for all S between 1 and min(N,M).  My expressions solves for the whole sum, where yours is only for a particular square size.

Commented:
A non-formulaic approach...

You first multiply width times height of the entire rectatngle (or height times width, it doesn't matter) (e.g. 4 x 3 = 12)
Then, reduce each number by 1 and multiply again (e.g. 3 x 2 = 6)
Reduce each number by 1 again, and multiply again (e.g. 2 x 1 =2).

Keep reducing and multiplying, until one of the numbers hits 0.  Then, add all the products: in the example above, 12 + 6 + 2 = 20.
CERTIFIED EXPERT
Top Expert 2009

Commented:
Take a look at the first post, Galisteo8 ...

Commented:
Oops. Thanks, infinity. I'm late to the party. :)

Commented:
Infinity has pretty well pegged it for you...
As the size of your "squares" increase, the size of the matrix you are "dealing with" effectively decreases...
If you were writing it as a program, a for loop to reduce the variables, and since the variables are not necessarily equal, an if to exit the for loop when either of the resulting reductions reachs zero...
In the meantime, multiply the variables and total the results.

Commented:
> No. of squares of dimension 2 is 6

Question is more like rectangles than squares, still that is incorrect. Taking

__________________________
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|

I think you are missing these:

__________________________
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|        2      |                  |        2      |
|________|_________|________|
|                |                  |                |
|        2      |                  |        2      |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|

etc
Data Warehouse / Database Architect
CERTIFIED EXPERT

Commented:

Hi Sunbow,

6 is correct.

___________________________
|                |                  |                |
|      A        |        B        |       C       |
|________|_________|________|
|                |                  |                |
|      D        |        E        |       F       |
|________|_________|________|
|                |                  |                |
|     G         |        H        |      I        |
|________|_________|________|
|                |                  |                |
|      J         |        K        |      L        |
|________|_________|________|

2x2 squares can only be inserted (defined) such that their upper left small square is coincidental with A, B, D, E, G, and H.

Kent

Commented:
Mybe it is design or image, and seeing what is rectangle or not while open to "these values from user"

I pretty much stopped review where AD is square, and imagine that you presume that. So I bow out Thanks This is then a math question, not puzzle.
Unlock the solution to this question.