# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# Problem 85
# ==========
#
# By counting carefully it can be seen that a rectangular grid measuring 3
# by 2 contains eighteen rectangles:
#
# ![https://projecteuler.net/project/images/p085.png](https://projecteuler.net/project/images/p085.png)
#
# Although there exists no rectangular grid that contains exactly two
# million rectangles, find the area of the grid with the nearest solution.

# +
from itertools import combinations

def num_sub_rectangles(x, y):
    return (x * y * (x + 1) * (y + 1)) // 4

def solve(n):
    x, y, closest = 0, 0, n
    for i, j in combinations(range(1, 100), 2):
        res = abs(num_sub_rectangles(i,j) - n)
        if res < closest:
            x, y, closest = i, j, res
    
    return x * y
           
# %timeit solve(2000000)
# -



StarcoderdataJupyterScriptsDedupFiltered