I have been reading the book grokking algorithms and I found an interesting challenge whilst learning the divide and conquer algorithm / technique, where the full solution had not been provided. So I wanted to implement this to ensure I understood it correctly.

To solve a problem using divide and conquer there are two steps:

1. Figure out the base case. This should be the simplest possible case.
2. Divide or decrease your problem until it becomes the base case.

To divide and decrease the problem it is common to use recursion and this algorithm was no different.

I have written another post that goes more in depth into recursion, which is also an implementation of D&C.

The problem (from the book):

Suppose you’re a farmer with a plot of land. 1680 meters x 640 meters. You want to divide this farm evenly into square plots. You want the plots to be as big as possible.

So basically we want to divide an area with a certain X & Y and divide it into the largest equal squares possible.

Along with recursion, the book explains that Euclid's algorithm will help us solve this problem.

Explanation of Euclid's algorithm from the book: If you find the biggest box that will work for this size, that will be the biggest box that will work for the entire farm. To understand why this is true, you can check this link to the Khan Academy.

So for help with implementing this solution, I looked for a Javascript implementation of the Euclidian algorithm, and came across this post Find the Great Common Divisor in Javascript . This was really the meat of what I needed for my solution.

It showed how by using modulus within a recursive function you can find the greatest common divisor between two numbers. When the result of the modulus between the two numbers is 0, that means we've hit the base case.

Read this post for a more in depth understanding, as I will only being parroting much of what is there.

The one difference I faced for my problem is that I am not working with just numbers - I needed to find the greatest square divisor.

To achieve this I needed to check which of the X or Y had the greatest length. Then I had to find the remainder, assigning the longest side to the left-hand side operator of the modulus. It will recurse through until the remainder is 0, meaning both sides are equal - then I know I found my base case square.

So here is my solution:

function sideInfo(x, y) {
    return  (x > y) ? { largestSide: x, smallestSide:y } : { largestSide: y, smallestSide:x }
}

function findBaseCase(x, y){ 
    const { smallestSide, largestSide } = sideInfo(x, y);
    const remainder = (largestSide % smallestSide);
    return remainder === 0 ? smallestSide : findBaseCase(remainder, smallestSide);
}

Below is a working implementation for you to test.

If you feel there is anything wrong with my explanation or it can be improved in anyway, please comment or reach out to me.