Try every possible width from 1 to area, check if it divides the area evenly, and track the pair [L, W] with the smallest difference where L >= W.
Start from floor(sqrt(area)) and decrement until we find a width that evenly divides the area. This guarantees the closest pair to a square.
""" 0492.1 - Solution 1 - Brute Force Approach """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def constructRectangle(self, area: int) -> List[int]:
"""Construct the Rectangle Function"""
best = [area, 1]
for w in range(1, area + 1):
if w * w > area:
break
if area % w == 0:
l = area // w
best = [l, w]
return best
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().constructRectangle(4)) # [2, 2]
print(Solution().constructRectangle(37)) # [37, 1]
print(Solution().constructRectangle(122122)) # [427, 286]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0492.2 - Solution 2 - Square Root Optimization """
#####################################################################################
# Imports
#####################################################################################
from typing import List
import math
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def constructRectangle(self, area: int) -> List[int]:
"""Construct the Rectangle Function"""
w = int(math.isqrt(area))
while area % w != 0:
w -= 1
return [area // w, w]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().constructRectangle(4)) # [2, 2]
print(Solution().constructRectangle(37)) # [37, 1]
print(Solution().constructRectangle(122122)) # [427, 286]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()