Skip to content

Instantly share code, notes, and snippets.

@EXayer
Last active June 23, 2020 21:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save EXayer/9a2f5957b3cada15b045b50d11c57c0b to your computer and use it in GitHub Desktop.
Save EXayer/9a2f5957b3cada15b045b50d11c57c0b to your computer and use it in GitHub Desktop.
<?php
/**
* Counts squares in matrix by loop.
*
* @param int $n
* @param int $m
* @return int
*/
function countSquares(int $m, int $n): int
{
if ($n === 0 || $m === 0) {
return 0;
}
if ($n < $m) {
$side = $n;
$count = 0;
} else if ($n > $m) {
$side = $m;
$count = 0;
} else {
$side = $n - 1;
$count = 1;
}
while ($side > 0) {
for ($i = 0; $i <= $n - $side; $i++) {
for ($j = 0; $j <= $m - $side; $j++) {
if ($i + $side <= $n && $j + $side <= $m) {
$count++;
}
}
}
$side--;
}
return $count;
}
/**
* Counts squares in matrix by formula.
* @link https://www.geeksforgeeks.org/count-number-of-squares-in-a-rectangle/
*
* @param int $n
* @param int $m
* @return int
*/
function countSquaresFormula(int $m, int $n): int
{
if ($n < $m) {
list($m, $n) = array($n, $m);
}
return $m * ($m + 1) * (2 * $m + 1) / 6 + ($n - $m) * $m * ($m + 1) / 2;
}
$i = 0;
do {
printf("%dx%d = %d - %d\n", $i, $i, countSquares($i, $i), countSquaresFormula($i, $i));
printf("%dx%d = %d - %d\n", $i + 1, $i, countSquares($i + 1, $i), countSquaresFormula($i + 1, $i));
printf("%dx%d = %d - %d\n", $i, $i + 1, countSquares($i, $i + 1), countSquaresFormula($i, $i + 1));
} while ($i++ < 10);
// 0x0 = 0 - 0
// 1x0 = 0 - 0
// 0x1 = 0 - 0
// 1x1 = 1 - 1
// 2x1 = 2 - 2
// 1x2 = 2 - 2
// 2x2 = 5 - 5
// 3x2 = 8 - 8
// 2x3 = 8 - 8
// 3x3 = 14 - 14
// 4x3 = 20 - 20
// 3x4 = 20 - 20
// 4x4 = 30 - 30
// 5x4 = 40 - 40
// 4x5 = 40 - 40
// 5x5 = 55 - 55
// 6x5 = 70 - 70
// 5x6 = 70 - 70
// 6x6 = 91 - 91
// 7x6 = 112 - 112
// 6x7 = 112 - 112
// 7x7 = 140 - 140
// 8x7 = 168 - 168
// 7x8 = 168 - 168
// 8x8 = 204 - 204
// 9x8 = 240 - 240
// 8x9 = 240 - 240
// 9x9 = 285 - 285
// 10x9 = 330 - 330
// 9x10 = 330 - 330
// 10x10 = 385 - 385
// 11x10 = 440 - 440
// 10x11 = 440 - 440
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment