We help IT Professionals succeed at work.

count squares of different dimensions in a matrix

1,009 Views
Last Modified: 2008-05-24
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.

So, can anyone please help me with the logic?
Thanks.
Comment
Watch Question

CERTIFIED EXPERT
Top Expert 2009
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION
jkr
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)
Kent OlsenData Warehouse / Database Architect
CERTIFIED EXPERT
Commented:
Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION
Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION
Kent OlsenData Warehouse / Database Architect
CERTIFIED EXPERT

Commented:
Hi NovaDenizen,

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
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.
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 ...
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
Kent OlsenData 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.
Thanks for using Experts Exchange.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.