Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

count squares of different dimensions in a matrix

Posted on 2007-10-11
14
Medium Priority
?
961 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.
0
Comment
Question by:shilpi84
  • 3
  • 3
  • 2
  • +4
14 Comments
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 600 total points
ID: 20059273
>> No. of squares of dimension 1 is 12

12 = 3 * 4

>> No. of squares of dimension 2 is 6

6 = (4 - 1) * (3 - 1)

>> No. of squares of dimension 3 is 2

2 = (4 - 2) * (3 - 2)

>> No. of squares of dimension 4 is 0

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


You see the pattern ?
0
 
LVL 86

Expert Comment

by:jkr
ID: 20059287
Well, the number of squres of the dimension 1*1 in a m*n-sized rectangle will always be m*n*...
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20059321
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)
0
Who's Defending Your Organization from Threats?

Protecting against advanced threats requires an IT dream team – a well-oiled machine of people and solutions working together to defend your organization. Download our resource kit today to learn more about the tools you need to build you IT Dream Team!

 
LVL 46

Assisted Solution

by:Kent Olsen
Kent Olsen earned 400 total points
ID: 20059372
Hi shilpi84,

The logic is actually pretty easy, once you see the pattern.

In your diagram, imagine the 1x1 square with a lower-left corner beginning in the diagram's lower-left corner.  Now move it right 1.  It is the center box, bottom square.  Move it to the right one more time and its lower-right corner is coincidental with the diagram's lower-right cornet.

Now imagine the 2x2 square with a lower-left corner beginning in the diagrams lower-left corner.  Move the 2x2 square to the right 1.  Its lower-right corner is now coincidental with the diagram's lower-right corner.

That's the foundation for the math.  The number of positions that the square can occupy in a direction is the length of the direction (the diagram's leg), minus the length of the object (the square's side) plus 1.  (Assuming that the square is no longer than the shortest side of the diagram.

Algebraicallly, it looks like this:     DiagramLength - SquareLength + 1

Since the same hold true in both directions (horizontal and vertical) the number of squares of any size is solved by:

  (DiagramLength - SquareLength + 1) * (DiagramHeight - SquareHeight + 1)


Good Luck,
Kent
0
 
LVL 22

Accepted Solution

by:
NovaDenizen earned 1000 total points
ID: 20060682
I think shilipi is asking for a simple formula to perform this calculation for an arbitrary w and h.  

f(1,1) = 1  (just a single 1x1)
f(n,1) = n  (just n 1x1)

f(a,b) = f(b,a)

Now let's think about f(a+1,b) where a >= b, and how it compares to f(a,b)

There are b more 1x1 squares than f(a,b)
There are b-1 more 2x2 squares than f(a,b)
...
There is 1 more bxb square than f(a,b)

So, given a >= b, f(a+1,b) = (sum of j for j = 1 to b) + f(a,b)
f(a+1, b) = f(a,b) + b(b+1)/2

Let's compare f(a+1,a+1) to f(a,a).

There are 2a+1 more 1x1 squares than f(a,a)
There are 2a-1 more 2x2 squares
....
There are 3 more axa squares
There is 1 a+1 by a+1 square
Add all these squares together, and it works out to (a+1)^2 new squares.
So, f(a+1,a+1) = f(a,a) + (a+1)^2

So, starting from f(1,1) = 1, how do we calculate f(a,b) where a > b?

f(b,b) = 1 + (sum of i^2 for i = 1 to b)
f(b,b) = 1 + (sum of i^2 for i = 2 to b+1)
f(b,b) = sum of i^2 for i = 1 to b+1
f(b,b) = b(b+1)(2b+1)/6

f(b+1, b) = f(b,b) + b(b+1)/2
so, f(a,b) = f(b + (a-b), b) = f(b,b) + (a-b)*(b(b+1)/2)
 = b(b+1)(2b+1)/6 + (a-b)*(b(b+1)/2)

for f(4,3): 3*4*7/6 + 1*3*4/2  = 14 + 6 = 20

f(10,20) = f(20,10) = 10*11*21/6 + 10*10*11/2 = 385 + 550 = 935

Remember that b is the smaller number and a is the larger.


0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 20060746
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
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 20061006
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.
0
 
LVL 8

Expert Comment

by:Galisteo8
ID: 20152168
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.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20153579
Take a look at the first post, Galisteo8 ...
0
 
LVL 8

Expert Comment

by:Galisteo8
ID: 20155922
Oops. Thanks, infinity. I'm late to the party. :)
0
 
LVL 4

Expert Comment

by:dagesi
ID: 20323252
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.
0
 
LVL 24

Expert Comment

by:SunBow
ID: 20368794
> 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
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 20368838

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
0
 
LVL 24

Expert Comment

by:SunBow
ID: 20369742
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.
0

Featured Post

Who's Defending Your Organization from Threats?

Protecting against advanced threats requires an IT dream team – a well-oiled machine of people and solutions working together to defend your organization. Download our resource kit today to learn more about the tools you need to build you IT Dream Team!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

577 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question