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 ?

Solved

Posted on 2007-10-11

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.

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.

14 Comments

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 = (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)

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

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.

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

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.

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.

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

__________________________

| | | |

| | | |

|________|_________|______

| | | |

| | | |

|________|_________|______

| | | |

| | | |

|________|_________|______

| | | |

| | | |

|________|_________|______

I think you are missing these:

__________________________

| | | |

| | | |

|________|_________|______

| | | |

| 2 | | 2 |

|________|_________|______

| | | |

| 2 | | 2 |

|________|_________|______

| | | |

| | | |

|________|_________|______

etc

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

Title | # Comments | Views | Activity |
---|---|---|---|

C#: Compare two audio files and calculate matching percentage | 6 | 279 | |

Octane 98 vs 95 petrol / gasoline : mileage, pros & cons | 10 | 65 | |

Task manager indicates my c++ program memory consumption is growing? | 12 | 80 | |

Geomentry-Fundamental concepts | 6 | 36 |

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

Connect with top rated Experts

**15** Experts available now in Live!