Max square size for unknown number inside rectangle

by

Conceptually:

  • start with 1 square
  • For each additional square, if you don’t have
    room in your grid box so far, shrink
    the existing box just enough to make
    room for an additional row or column.

pseudocode: given M x N rectangle to fill with K squares

// initial candidate grid within the rectangle
h=1
w=1
maxsquares=1
size=min(M,N) //size of the squares
while K > maxsquares
  if M/(h+1) >= N/(w+1)
    h=h+1
  else
    w=w+1
  endif
  maxsquares=h*w
  size=min(M/h,N/w)
done
print size

There are probably faster ways to jump to the answer for very large K, but I can’t think of them. If you know that M and N are integers, there may be even faster methods.

More Related Contents:

  1. Is floating point math broken?
  2. Calculate distance between 2 GPS coordinates
  3. Understanding “randomness”
  4. Generate a random point within a circle (uniformly)
  5. Divide by 10 using bit shifts?
  6. A simple algorithm for polygon intersection
  7. Calculating area enclosed by arbitrary polygon on Earth’s surface
  8. Golang Round to Nearest 0.05
  9. Is Big O(logn) log base e?
  10. Overflow and Carry flags on Z80
  11. correcting fisheye distortion programmatically
  12. Implementing Ray Picking
  13. Calculate the center point of multiple latitude/longitude coordinate pairs
  14. Calculating a LookAt matrix
  15. How to use 4d rotors
  16. Is finding the equivalence of two functions undecidable?
  17. Evaluating a string of simple mathematical expressions [closed]
  18. Fitting polynomials to data
  19. Perpendicular on a line from a given point
  20. How to map atan2() to degrees 0-360
  21. Code Golf: Mathematical expression evaluator (that respects PEMDAS)
  22. Calculate second point knowing the starting point and distance
  23. “Average” of multiple quaternions?
  24. Why does floating-point arithmetic not give exact results when adding decimal fractions?
  25. Convert Linear scale to Logarithmic
  26. Calculate rotated rectangle size from known bounding box coordinates
  27. Designing function f(f(n)) == -n
  28. Why use softmax as opposed to standard normalization?
  29. How to perform division in Go
  30. Get direction (compass) with two longitude/latitude points

Leave a Comment