Best Grid Dimensions

# Best Grid Dimensions ## Difficulty Easy ## Tags `math` ## Problem Statement Given a positive integer `n`, find the dimensions `rows` and `cols` of a grid such that: 1. The grid can hold at least `n` elements (rows × cols ≥ n). 2. The dimensions are as close to a square as possible (minimize |rows - cols|). 3. Waste space (rows × cols - n) is minimized as a secondary goal. Return the dimensions as a tuple `(rows, cols)` where `rows ≤ cols`. ## Constraints - 1 ≤ n ≤ 10⁹ ## Signatures ### Python ```python def best_grid(n: int) -> Tuple[int, int]: pass ``` ### Java ```java public class Solution { public Object best_grid(int n) { return null; } } ``` ### Csharp ```csharp public class Solution { public Object best_grid(int n) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: Object best_grid(int n) { } }; ``` ### C ```c Object best_grid(int n) { } ``` ### Ruby ```ruby def best_grid(n) end ``` ### Perl ```perl sub best_grid { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def best_grid(n: Int): Object = { } } ``` ### Haskell ```haskell best_grid :: ... -> ... best_grid args = undefined ``` ### Clojure ```clojure (defn best_grid [n] ) ``` ### Scheme ```scheme (define (best_grid n) ) ``` ## Examples ### Example 1 **Input:** ``` n = 10 ``` **Output:** ``` (3, 4) ``` **Explanation:** 3 × 4 = 12 ≥ 10. The square root of 10 is ~3.16, so 3 × 4 is closest to square. (2 × 5 = 10 exactly, but |2-5|=3 vs |3-4|=1, so 3×4 is more square-like). ### Example 2 **Input:** ``` n = 16 ``` **Output:** ``` (4, 4) ``` **Explanation:** Perfect square. ### Example 3 **Input:** ``` n = 17 ``` **Output:** ``` (4, 5) ``` **Explanation:** 4 × 5 = 20 ≥ 17. Most square-like with 3 wasted spaces. ### Example 4 **Input:** ``` n = 1 ``` **Output:** ``` (1, 1) ``` ## Hints 1. Start with the integer square root of n. 2. This gives you the baseline for rows. 3. Calculate cols = ceil(n / rows). 4. Check if (rows-1, cols) or (rows, cols) gives a better (more square) result.