# the biggest square that fits

2023-11-10 · 3 min read · #algorithms

Source: https://jopcmelo.com/writing/the-biggest-square-that-fits

a farmer has a plot of land, 1680m by 640m, and wants to split it into equal square plots, as big as possible. how big?

you could try sizes until one fits. or you could shrink the problem until it's easy, which is what divide and conquer means:

1. find the base case: the simplest version, where the answer is obvious.
2. shrink the problem until it becomes the base case.

the base case here: if one side is a multiple of the other, the answer is the shorter side. a 50m by 25m plot is two 25m squares.

## shrinking the farm

the 1680m by 640m plot isn't a base case. so cut out the biggest squares that fit, 640m each: two of them, and a 400m by 640m strip is left. and here's the trick: **any square that splits that strip evenly also splits the whole farm evenly**, since the rest is made of 640m squares built on the same side. so now the problem is just the strip.

the biggest square in the strip is 400m, leaving 400m by 240m. then 240m, leaving 240m by 160m. then 160m, leaving 160m by 80m, and 160 is a multiple of 80. base case. the answer is 80m: the farm splits into 168 squares of 80m by 80m.

*(sketch: a 1680 by 640 meter farm. two 640 meter squares are cut out, then a 400, a 240, a 160, and two 80s. the cuts erase and draw themselves again, in order, over and over)*

that's [Euclid's algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) for the greatest common divisor, more than 2,000 years old. in code, the remainder does the cutting:

```javascript
function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

gcd(1680, 640); // 80
```

## one at a time, or halves

the same recipe works on code. adding up a list: the base case is an empty list, which adds up to 0. to shrink it, take one item off:

```javascript
function sum(list, i = 0) {
  if (i === list.length) return 0;
  return list[i] + sum(list, i + 1);
}
```

it works, and it's as deep as the list is long: every item is another call waiting on the [call stack](/writing/a-box-inside-a-box). with 100,000 numbers, Node gave up: `Maximum call stack size exceeded`.

shrink it by half instead, and the depth drops to the number of times the list can be halved:

```javascript
function sum(list, from = 0, to = list.length) {
  if (to - from === 0) return 0;
  if (to - from === 1) return list[from];
  const mid = Math.floor((from + to) / 2);
  return sum(list, from, mid) + sum(list, mid, to);
}
```

*(sketch: one at a time: a stack of calls 100,000 deep. halves: a short tree of calls, 18 deep)*

the same 100,000 numbers, 18 calls deep. **how you shrink the problem decides how deep you go.** it's the idea behind merge sort and [quicksort](/writing/pick-a-pivot), which split a list in two and sort each half the same way.

the code from the first version of this post, with more exercises, is in [my algorithms repo](https://github.com/joaopcm/algorithms/tree/main/divide-and-conquer).