Dividing area into a given number of squares

Question

I have a DIV Element that can be resized by the user. Into this DIV I want to draw a given number of squares. Now I need to find out, what the perfect side length for the square would be so that all fit into the DIV without overflowing.

This is what I got so far:

function CalcSize (){
    var number = 23; // Example-Number
    var area = jQuery('#container').height() * jQuery('#container').width();
    var elementArea = parseInt(area / number);
    var sideLength = parseInt(Math.sqrt(elementArea));
    return sideLength;
}

This makes the squares too big since it does not "throw away" the space that cannot be filled with the squares. By searching for this problem I found the Packing Problem and Treemapping but both did not help me with my problem, since honestly I lack the math skills and from what I understand the solutions allow things like non-squares and rotations.

Thanks!

Update:

I currently use a very crude method to resize the squares by constantly resizing them and looking if they overflow. This method gives me the correct result but is quite bad on the performance. I am sure that this can be achieved by calculations.

Answer 1

Here is an algorithm that will use the entire width and all unused space will be at the bottom. This will not always give the largest possible squares, but it will behave in a consistent manner and should look nice.

Note that the while loop should normally not go more than one or two iterations.

function CalcSize (){
    var number = 23; // Example-Number
    var width = jQuery('#container').width();
    var height = jQuery('#container').height();
    var area = height * width;
    var elementArea = parseInt(area / number);

    // Calculate side length if there is no "spill":
    var sideLength = parseInt(Math.sqrt(elementArea));

    // We now need to fit the squares. Let's reduce the square size 
    // so an integer number fits the width.
    var numX = ceil(width/sideLength);
    sideLength = width/numX;
    while (numX <= number) {
        // With a bit of luck, we are done.
        if (floor(height/sideLength) * numX >= number) {
            // They all fit! We are done!
            return sideLength;
        }
        // They don't fit. Make room for one more square i each row.
        numX++;
        sideLength = width/numX;
    }
    // Still doesn't fit? The window must be very wide
    // and low.
    sideLength = height;
    return sideLength;
}

Answer 2

Based on the image, I made an assumption that you are ok with both vertical and horizontal unused spaces, as long as the length is maximized.

Basically this is a Linear Programming problem (well actually it is Integer Programming Problem). We have following inequalities and we want to maximize length.

rows,cols, and length are unknowns; and n, width, and height are given:

rows >= 1
cols >= 1
rows*cols >= n
rows*length <= height
cols*length <= width
maximize length

From the last 3 equations you got the estimate right: length <= sqrt(height*width/n). You would still need to loop over the possible range to get the integer values though. You can do that a lot faster with Binary Search.