FastPrep
Problem · Sorting

Maximize Total Area of Rectangles (SDE 2)

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

Amazon games have introduced a new mathematical game for kids. You will be given n sticks and the player is required to form rectangles from those sticks.

Formally, given an array of n integers representing the lengths of the sticks, you are required to create rectangles using those sticks. Note that a particular stick can be used in at most one rectangle and in order to create a rectangle we must have exactly two pairs of sticks with the same lengths. For example, you can create a rectangle using sticks of lengths [2, 2, 5, 5] and [4, 4, 4, 4] but not with [3, 3, 5, 8]. The goal of the game is to maximize the total sum of areas of all the rectangles formed.

In order to make the game more interesting, we are allowed to reduce any integer by at most 1. Given the array sideLengths, representing the length of the sticks, find the maximum sum of areas of rectangles that can be formed such that each element of the array can be used as length or breadth of at most one rectangle and you are allowed to decrease any integer by at most 1. Since this number can be quite large, return the answer modulo 10^9+7.

Note: It is not a requirement that all side lengths be used. Also, a modulo b here represents the remainder obtained when an integer a is divided by an integer b.

Function

getMaxTotalArea(sideLengths: int[]) → int

Complete the function getMaxTotalArea in the editor.

getMaxTotalArea has the following parameter(s):

  1. int sideLengths[n]: the side lengths that can be used to form rectangles

Returns

int: the maximum total area of the rectangles that can be formed, modulo (109+7).

🪻༊·°Credit to niketpatel3𓂃🖊

Examples

Example 1

sideLengths = [2, 6, 2, 6, 3, 5]return = 12
The lengths 2, 2, 6, and 6 can be used to form a rectangle of area 2*6=12. No other rectangles can be formed with the remaining lengths. The answer is 12 modulo (109+7)=12.

Example 2

sideLengths = [2, 3, 3, 4, 6, 8, 8, 6]return = 54
Two rectangles can be formed. One has sides of 6 and 8, and the other by reducing 4 and one of the 3s by 1 has sides of 2 and 3. The total area of these rectangles is (6*8+2*3) mod (109+7) = 54.

Example 3

sideLengths = [3, 4, 5, 5, 6]return = 20
The rectangle can have either sides of 5 and 3 (reduce 4 by 1), or sides of 5 and 4 (reduce 6 and one 5 by 1). The second option has a greater area, so 5*4 > 3*5.

Constraints

  • 1 ≤ n ≤ 105
  • 2 ≤ sideLengths[i] ≤ 104 where 0 ≤ i < n

    • More Amazon problems

    drafts saved locally
    public int getMaxTotalArea(int[] sideLengths) {
  // write your code here
}
    sideLengths[2, 6, 2, 6, 3, 5]
    expected12
    checking account