Project Euler Problem 85 Statement

By counting carefully it can be seen that a rectangular grid measuring $3$ by $2$ contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

Solution

We are going to find an n × m grid such that the number of sub-rectangles is as close as possible to a given target. Once we find such dimensions, we return the grid's area n × m.

Recall that the number of sub-rectangles in an n × m grid is $$T_n \times T_m = \frac{n(n+1)}{2} \times \frac{m(m+1)}{2}.$$

1. Precomputing Triangular Numbers

import bisect, itertools
tn = list(itertools.accumulate(range(1, 2001)))

• Create a precomputed list, tn[], for the first 2000 triangular numbers. $$[\,1,\; 1+2,\; 1+2+3,\; \dots,\; 1+2+\dots+2000\,]$$ $$tn[0] = 1,\quad tn[1] = 3,\quad tn[2] = 6,\;\dots$$
• We only need 2,000 triangular numbers because or limit for target is 2,000,000.
• $T_{2000} = \frac{2000\times 2001}{2} = 2,001,000$, which is aready $\gt 2,000,000$.

2. The closest_area() Function

def closest_area(target):
    left, right = 0, bisect.bisect_left(tn, target)
    best_area, min_diff = 0, float('inf')
    while left <= right:
        count = tn[left] * tn[right]
        diff = abs(count - target)
        area = (left + 1) * (right + 1)

        if diff < min_diff or (diff == min_diff and area > best_area):
            best_area, min_diff = area, diff

        if count > target:
            right -= 1
        else:
            left += 1

    return best_area

1. Initialization:
   left = 0 and right = bisect.bisect_left(tn, target). This sets the initial boundaries for our two-pointer search in the list of triangular numbers. We also track the best candidate with best_area = 0 and min_diff = float('inf').

2. Two-Pointer Search:
   Naively checking all pairs m and n could be slow. By using a two-pointer method on a sorted array of triangular numbers, we can more efficiently zero in on products that are close to target.

   • If the product is too large, move the right pointer left.
   • If the product is too small or just right, move the left pointer right.
   • As we move the pointers, we keep track of the smallest difference from target. In case of a tie, we prefer the grid with the larger area.
   In each iteration:
   • count = tn[left] * tn[right] computes $$\frac{(left+1)(left+2)}{2} \times \frac{(right+1)(right+2)}{2}.$$
   • diff = abs(count - target) measures how close this product is to target.
   • area = (left + 1) * (right + 1) is the actual area $(m\times n)$ of the candidate grid.
   • We update best_area if this difference diff is the smallest so far (or if it ties for smallest, but yields a larger area):

     if diff < min_diff or (diff == min_diff and area > best_area):
         best_area, min_diff = area, diff
     

   • If count > target, we move right -= 1 to try reducing the product. Otherwise, left += 1 to try increasing the product.
3. Result:
   When left <= right is no longer true, we exit the loop and return best_area, which is the area of the grid whose sub-rectangle count is closest to target.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 85

HackerRank Project Euler 85: For each testcase an integer target would be given . Consider all the rectangular grids such that the number of rectangles contained in the grid is nearest to target . Out of all such rectangular grids output the area of the rectangular grid having the largest area.